# Shared Flashcard Set

## Details

Systems of Linear Equations
Math Background; Norms and Conditioning; Gaussian Elimination; Symmetric Matrices; Sparse Linear Systems; Stationary Iterative Methods; CG method
51
Computer Science
03/02/2014

Term
 Vector Spaces
Definition
 A set of vectors over a field of scalars that is closed under vector addition and scalar multiplication. [image]
Term
 Subspace
Definition
 A subset of a vector space that is closed under addition and scalar multiplication
Term
 Linear Independence
Definition
 A set of vectors in which none can be written as a linear combination of each other
Term
 Rank
Definition
 The number of linear independent columns of a matrix
Term
 Dimension
Definition
 A matrix with m rows and n columns (m x n matrix) -- m and n are the dimensions
Term
 Span(S)
Definition
 The set of all finite linear combinations of the elements of S
Term
 Basis
Definition
 Set of linearly independent vectors that can represent (in a linear combination) every vector in a given vector space
Term
 Null Space
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
 Determinant
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
 Nonsingular
Definition
 A has an inverse det(A) does not equal 0 Rank(A) = n For any nonzero vector z, Az cannot equal 0
Term
 Permutation Matrix
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
 Transpose
Definition
 The transpose of M, MT is the matrix whose columns are the rows of M
Term
 Conjugate Transpose
Definition
 If B is equal to the conjugate transpose of A, for all aij in A, bij = āij.
Term
 Symmetric Matrices
Definition
 A = AT
Term
 Hermitian Matrices
Definition
 A = AH (the conjugate transpose)
Term
 Partitioned Matrices
Definition
 Blocked matrix, can be interpreted as having been broken into sections/submatrices.
Term
 Vector norm
Definition
 [image]
Term
 Matrix Norm
Definition
 [image]
Term
 Condition number of a matrix
Definition
 Cond(A) = ||A|| ||A-1|| = σmax/σmin
Term
 Conditioning of Ax = b with perturbed b
Definition
 [image][image]
Term
 Conditioning of Ax = b with perturbed A (A+E)
Definition
 [image][image]
Term
 Residual vs. Error
Definition
 [image]   [image][image]
Term
 LU factorization
Definition
 [image]
Term
 Partial Pivoting
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
 Complete Pivoting
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
 Growth Factor
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
 Scaling
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
 Diagonal Dominance
Definition
 The absolute value of the diagonal entry is greater than the sum of the absolute values of the off-diagonals
Term
 Iterative Refinement
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
 Gauss-Jordan Elimination
Definition
 Instead of reducing to triangular form, reduce to diagonal.  Annihilate above and below the diagonal with elementary elimination matrix.  50% more expensive.
Term
 Rank-one updating
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
 For all x, xTAx > 0
Term
 Cholesky Factorization
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
 Band Matrices
Definition
 a[i,j] = 0 for all |i-j| > bandwidth.  Tridiagonal matrices are banded with bandwidth of 1
Term
 Sparse Storage Schemes
Definition
 COO -- coordinate format: 3 arrays -- data, column indices, row indices CSR -- compressed sparse row: 3 arrays -- data, column indices, row pointer
Term
 Graph of a Matrix
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
 Fill
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
 Reordering for sparsity
Definition
 Can reorder matrix to limit the amount of fill.  Making banded will result in less fill.
Term
 Minimum Degree
Definition
 Eliminate first the entries having the fewest neighbors, resulting in minimal fill.
Term
 Nested Disection
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
 Jacobi
Definition
 xk+1 = D-1(b - (L+U)xk)
Term
 Gauss-Seidel
Definition
 xk+1 = D-1(b - Lxk+1 - Uxk)
Term
 Successive Over Relaxation (SOR)
Definition
 xk+1 = xk + ω(xkGS -xk)
Term