Term
|
Definition
A set of vectors over a field of scalars that is closed under vector addition and scalar multiplication.
[image] |
|
|
Term
|
Definition
| A subset of a vector space that is closed under addition and scalar multiplication |
|
|
Term
|
Definition
| A set of vectors in which none can be written as a linear combination of each other |
|
|
Term
|
Definition
| The number of linear independent columns of a matrix |
|
|
Term
|
Definition
| A matrix with m rows and n columns (m x n matrix) -- m and n are the dimensions |
|
|
Term
|
Definition
| The set of all finite linear combinations of the elements of S |
|
|
Term
|
Definition
| Set of linearly independent vectors that can represent (in a linear combination) every vector in a given vector space |
|
|
Term
|
Definition
For some function L(v), all vectors v such that L(v) = 0.
For a matrix A, all vectors x such that Ax = 0. |
|
|
Term
|
Definition
| Nonsingular when Det(A) is nonzero. The absolute value of the determinant gives the scale factor by which area, volume, etc. is multiplied under associated linear transformation. |
|
|
Term
| Existence and uniqueness of solutions to linear systems |
|
Definition
| For nxn matrix A, there is a unique solution to Ax = b if A is nonsingular. Otherwise, there are infinitely many solutions if b is in the span of A, and no solutions if it is not. |
|
|
Term
|
Definition
- A has an inverse
- det(A) does not equal 0
- Rank(A) = n
- For any nonzero vector z, Az cannot equal 0
|
|
|
Term
|
Definition
| A square matrix having exactly one 1 in each row and columns, and zeros elsewhere. Inverse is equal to transpose. Premultiplying permutes rows. Postmultiplying permutes columns. |
|
|
Term
|
Definition
| The transpose of M, MT is the matrix whose columns are the rows of M |
|
|
Term
|
Definition
| If B is equal to the conjugate transpose of A, for all aij in A, bij = āij. |
|
|
Term
|
Definition
|
|
Term
|
Definition
| A = AH (the conjugate transpose) |
|
|
Term
|
Definition
| Blocked matrix, can be interpreted as having been broken into sections/submatrices. |
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
| Condition number of a matrix |
|
Definition
Cond(A) = ||A|| ||A-1||
= σmax/σmin |
|
|
Term
| Conditioning of Ax = b with perturbed b |
|
Definition
|
|
Term
| Conditioning of Ax = b with perturbed A (A+E) |
|
Definition
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
|
Definition
| Before eliminating below the diagonal in each column, permute the matrix so that entry with largest magnitude on or below the diagonal becomes the diagonal entry. |
|
|
Term
|
Definition
| Before eliminating below diagonal, look at entire submatrix to lower right. Choose largest entry in submatrix and permute so that this entry becomes new diagonal value. |
|
|
Term
|
Definition
The ratio of the largest entry of U to the largest entry of A (in magnitude). Without pivoting, can be arbitrarily large. With pivoting can be 2n-1.
[image] |
|
|
Term
|
Definition
| Premultiplying both sides of Ax=b by a nonsingular diagonal matrix multiplies each row of the matrix and right hand side by the corresponding diagonal entry -- row scaling |
|
|
Term
|
Definition
| The absolute value of the diagonal entry is greater than the sum of the absolute values of the off-diagonals |
|
|
Term
|
Definition
After LU you have some x0. So, r0=b-Ax0. Use previous LU factors to solve As0=x0, x1=x0+s0.
Can iteratively improve the solution. |
|
|
Term
|
Definition
| Instead of reducing to triangular form, reduce to diagonal. Annihilate above and below the diagonal with elementary elimination matrix. 50% more expensive. |
|
|
Term
|
Definition
| Addition or subtraction of an nxn matrix that is an outer product uvT... rank one update. Don't need to recompute LU. Can instead use Sherman Morrison formula |
|
|
Term
| Symmetric Positive Definite Matrices |
|
Definition
|
|
Term
|
Definition
For SPD matrices, A = LLT. Can be derived by equating the corresponding entries of A and LLT and then generating the entries of L in correct order.
O(n3/6) -- 50% less work and storage than LU |
|
|
Term
| Symmetric Indefinite Systems |
|
Definition
| Symmetric, but not positive definite, some form of pivoting is required (cant use Cholesky). Must have symmetric pivoting PAPT = LDLT with D tridiagonal or block diagonal (with 1x1 or 2x2 blocks). |
|
|
Term
|
Definition
| a[i,j] = 0 for all |i-j| > bandwidth. Tridiagonal matrices are banded with bandwidth of 1 |
|
|
Term
|
Definition
COO -- coordinate format: 3 arrays -- data, column indices, row indices
CSR -- compressed sparse row: 3 arrays -- data, column indices, row pointer |
|
|
Term
|
Definition
| Edges between two vertices (i,j) of a graph means there is a nonzero entry in the matrix at A[i,j]. If undirected, symmetric matrix. |
|
|
Term
| Graph Interpretation of Elimination |
|
Definition
When an entry is eliminated, all neighbors of that node in the graph become connected == Fill
|
|
|
Term
|
Definition
| When entries are removed from a sparse matrix (say, to make it upper triangular), nonzero entries are added to the lower triangular portion of the matrix that were previously zero. |
|
|
Term
|
Definition
| Can reorder matrix to limit the amount of fill. Making banded will result in less fill. |
|
|
Term
|
Definition
| Eliminate first the entries having the fewest neighbors, resulting in minimal fill. |
|
|
Term
|
Definition
| Divide-and-conquer. First remove nodes who split mesh into two pieces. Repeat recursively. |
|
|
Term
| Stationary Iterative Methods |
|
Definition
xk+1 = Gxk + c, where G and c are chosen so that g(x) = Gx + c is a solution to Ax = b. G and x are constant over all iterations.
xk+1 = M-1Nxk + M-1b |
|
|
Term
|
Definition
| Eigenvalue of maximum magnitued. If < 1, converges; smaller = faster convergence. |
|
|
Term
|
Definition
|
|
Term
|
Definition
| xk+1 = D-1(b - Lxk+1 - Uxk) |
|
|
Term
| Successive Over Relaxation (SOR) |
|
Definition
|
|
Term
|
Definition
|
|
Term
|
Definition
| Converges in far fewer than n iterations |
|
|
Term
| CG Conjugate Search Directions |
|
Definition
| The successive search directions are A-orthogonal (conjugate), and hence satisfy a 3 term recurrence. |
|
|
