Questions tagged [gaussian-elimination]
The gaussian-elimination tag has no usage guidance.
13
questions
29
votes
2
answers
696
views
Gaussian elimination is just Gram-Schmidt with a change to the inner product symbol?
I noticed at some point that if you take the Gram-Schmidt algorithm for taking the QR decomposition of a matrix, and you change the meaning of the inner product symbol $\langle \mathbf u, \mathbf v \...
- 4,416
9
votes
2
answers
186
views
Solving systems of linear equations without introducing negative numbers
Consider a system of $n$ linear equations with $n$ unknowns, all of whose coefficients and right hand sides are nonnegative integers, with a unique solution consisting of nonnegative rational numbers. ...
- 18.8k
0
votes
0
answers
30
views
The backward error of tridiagonal linear system $Ax=b$ by Gaussian elimination without pivoting
Let $A$ be an $n \times n$ nonsingular tridiagonal matrix having an $LU$
factorization. It can be shown that the computed solution of the linear system
$Ax = b$ using Gaussian elimination without ...
- 53
1
vote
0
answers
46
views
Block matrix reduce system for finite element method
To solve a problem using the finite element method, we make a big matrix "connecting" many small matrix, each is computed using one element, like
$$
\underbrace{\begin{bmatrix}
\square & ...
- 223
1
vote
0
answers
95
views
Does fraction-free Gaussian elimination use fractional row operations?
I would like to understand whether Gaussian elimination of an integer matrix, which uses only row operations of the form
Addition (or subtraction) of row $i$ to row $j$
can be performed in ...
- 111
0
votes
0
answers
89
views
Exact Gaussian elimination of a rational matrix
If a matrix $A$ consists of rational elements, and we have access to only row operations of the form
Row addition/subtraction from row $i$ to row $j$
Row exchanging row $i$ with row $j$
What is the ...
- 111
2
votes
1
answer
57
views
Linear system of equations with prior knowledge on linear dependency of some unknowns
Assume I have a system of linear equations $Au = b$ where A is some $M\times N$ matrix, u is $N\times 1$ unknown variables vector, and b is $M\times 1$. Now, further assume that I know that some ...
- 173
3
votes
2
answers
1k
views
Methods of solving linear system of equations, how to select the appropriate method
A linear system of equations Ax=b can be solved using various methods, namely, inverse method, Gauss/Gauss-Jordan elimination, LU factorization, EVD (Eigenvalue Decomposition), and SVD (Singular Value ...
- 131
2
votes
2
answers
131
views
fast way to calculate normal to set of vectors with $\pm$1 entries
Say I have a set of $(n-1)$ linearly independent vectors $\mathbf{v}_i$ of dimension $n$ with entries $\pm1$. I am interested in finding the $n-$dimensional vector $\mathbf{u} $which is normal to the ...
- 283
2
votes
0
answers
82
views
Scale vector in scaled pivoting (numerical methods)
I'm teaching students about several numeric methods, including scaled pivoting. There's a small section in this subject that I could never find a clear explanation to, either as intuition, or a more ...
- 121
1
vote
0
answers
138
views
Can we give efficiently the solution of a bilinear system of equations over a finite field?
Consider a finite field $F$ and suppose we have a system of equations
$$h_1(\alpha,\beta)=0,h_2(\alpha,\beta)=0,...,h_t(\alpha,\beta)=0$$
where $\alpha=(\alpha_1,...,\alpha_s)$ and $\beta=(\beta_1,.....
- 131
3
votes
2
answers
188
views
Cases of almost-linear time solvable linear systems
Let a square $n\times n$ real matrix ${\bf A}$ and two vectors ${\bf x}$ and ${\bf b}$ of length $n$, such that $${\bf A}{\bf x}={\bf b}.$$
Solving for ${\bf x}$ through standard Gaussian Elimination ...
- 429
5
votes
2
answers
451
views
Left U_n-invariants of SL_n - an exercise in Kraft-Procesi
I am sorry for spamming MO with questions I have not thought about for more than 3 hours, but currently I am quite busy with preparing a talk on representations of $S_n$, and I don't want these to get ...
- 31.8k