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, M^{T }is the matrix whose columns are the rows of M 


Term

Definition
If B is equal to the conjugate transpose of A, for all a_{ij} in A, b_{ij} = āij. 


Term

Definition


Term

Definition
A = A^{H} (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 2^{n1}.
[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 offdiagonals 


Term

Definition
After LU you have some x_{0}. So, r_{0}=bAx_{0}. Use previous LU factors to solve As_{0}=x_{0}, x_{1}=x_{0}+s_{0}.
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 uv^{T}... 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 = LL^{T}. Can be derived by equating the corresponding entries of A and LL^{T} and then generating the entries of L in correct order.
O(n^{3}/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 PAP^{T} = LDL^{T} with D tridiagonal or block diagonal (with 1x1 or 2x2 blocks). 


Term

Definition
a[i,j] = 0 for all ij > 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
Divideandconquer. First remove nodes who split mesh into two pieces. Repeat recursively. 


Term
Stationary Iterative Methods 

Definition
x_{k+1} = Gx_{k} + 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.
x_{k+1} = M^{1}Nx_{k} + M^{1}b 


Term

Definition
Eigenvalue of maximum magnitued. If < 1, converges; smaller = faster convergence. 


Term

Definition
x_{k+1} = D^{1}(b  (L+U)x_{k}) 


Term

Definition
x_{k+1} = D^{1}(b  Lx_{k+1}  Ux_{k}) 


Term
Successive Over Relaxation (SOR) 

Definition
x_{k+1} = x_{k} + ω(x_{k}^{GS} x_{k}) 


Term

Definition


Term

Definition
Converges in far fewer than n iterations 


Term
CG Conjugate Search Directions 

Definition
The successive search directions are Aorthogonal (conjugate), and hence satisfy a 3 term recurrence. 

