Math 510: Numerical Methods for Linear Algebra

Catalog Information

Title

Numerical Methods for Linear Algebra.

Credit Hours

3

Prerequisite

Math 343, 410; or equivalents.

Description

Numerical matrix algebra, orthogonalization and least squares methods, unsymmetric and symmetric eigenvalue problems, iterative methods, advanced solvers for partial differential equations.

Desired Learning Outcomes

Prerequisites

Mastery of materials in an undergraduate course in linear algebra. Knowledge of matlab.

Minimal learning outcomes

(Must know)

Know properties of unitary matrices
Know general definition of norms and specific definition of vector $p$-norms for 1<=p< infinity
Know general definition of induced matrix norms and specific definitions of 1-,2- and infinity-norms 
Know  norm of product of matrices  $\leq $  product of norms of each matrix
Know invariance of 2-norm and Frobenius norm of a matrix under multiplication by a unitary matrix
Know definition of singular values and left and right singular vectors 
State the  existence and uniqueness of SVD 
Be able to find 2-norm and Frobenius norm given singular values of a matrix  
Be able to represent a matrix  as a sum of rank-one matrices  
Know truncated rank-one sum gives the best lower rank approximation to a matrix  
Know definitions of projectors,  complementary projectors and orthogonal projectors
be able to state and apply  classical Gram-Schmidt and modified Gram-Schmidt algorithms
Know definition and properties of a Householder reflector
Know how to construct Householder reflectors to triangularize a matrix
Know the Householder QR factorization for triangularizing a matrix
Know how least squares problems arise from a polynomial fitting problem
Know how to solve least square problems using  normal equations/pseudoinverse , QR factorization and SVD
Be able to define the condition of a problem and related condition number
Know how to calculate the condition number of a matrix (using norms and using singular values)
Understand the concepts of well-conditioned and ill-conditioned problems
 Know how to derive the conditioning bound of matrix-vector multiplication/ linear system solve
Be able to state the precise definition of stability and backward stability
Know the difference between stability and conditioning
Know the four condition numbers of a least squares problem  
Know how to construct element matrices to represent row operations
Understand LU  and PLU factorizations
Know how permutation matrices are used to represent row and column swap
Understand how pivots are selected in partial pivoting 
Know how PLU is represented by permutation matrices and elementary matrices  
 Know similarity transformation preserves eigenvalues
Know nondefective matrices have an eigenvalue decomposition (i.e. diagonalizable)
Understand why and how matrices can be reduced to Hessberg form (or for real symmetric matrices, to tridiagonal form) using Householder reflectors while preserving eigenvalues
Be able to state and prove the convergence of power method
 Know what Rayleigh quotient is nd its relation to eigenvalues
Be able to describe inverse iteration and Rayleigh quotient iteration
Know the convergence rates for eigenvalue/vector of  Rayleigh quotient iteration
Understand Rayleigh quotient as stationary points of $r(x)$
Know what normal matrices are
Be able to state the QR algorithm (without and with shifts) and now why shifts are needed
Know how to find Rayleigh quotient shifts and Wilkinson shifts
Know how to find Rayleigh quotient shifts 
Be able to state the simultaneous iteration algorithm
Understand simultaneous iteration and QR alogirthm are mathematically equivalent  
Be able to describe Arnoldi algorithm
Know reduced QR factors of Krylov matrix obtained from Arnoldi iterations  
Know characteristic polynomial of $H_{n}$ in Arnoldi iteration satisfies a minimization problem  
Be able to state the GMRES algorithm
Be able to describe the leas squares problem that needs to be solved in a GMRES iteration
Be able to state three term recurrence of Lanczos iteration for real symmetric matrices
State the CG algorithm for a real SPD matrix
Be able to derive the step length parameter in line search and construction of new search directions in CG
Be about the describe the v-cycle multigrid algorithm and the full multigrid algorithm
Understand  relaxation, nested multiplication and coarse grid correction
Understand how information is transferred between uniform grids using prolongation and restriction for 1D problems

(Important to know)

Know  inner product and outer product
Know Cauchy-Schwarz and Holder inequalities
Know difference between reduced and full SVD
Know relation between singular vectors and eigenvectors for Hermitian $A$
Know relation between determinant of a square matrix and its singular values 
Know relationship between mathematical/ numerical rank  and singular values  
Know relation among range, null space  and singular vectors  
Know characterization of orthogonal projector  
Know  reduced and full QR factorizations
Know existence of QR factorization  
Be able to express classical Gram-Schmidt and modified Gram-Schmidt algorithms in terms of projectors
Write Gram-Schmidt as a QR factorization
Know classical Gram-Schmidt algorithm is unstable (loss of orthogonality) but  modified Gram-Schmidt algorithm is stable
Know solution of least square problem has its residual orthogonal to the range of  matrix  
Know pseudo-inverse and its relation to least squares problem
Be able to state the fundamental axiom of floating point arithmetic
Understand the big Oh notation
Know that QR factorization via Householder factorization is backward stable
Be able to derive the conditioning bounds for a least squares problem when the vector $b$ is perturbed.  
Know solution using SVD and QR factorization   (both via Householder or Gram-Schmidt)  is backward stable
Know solution to normal equations  is unstable
Know how PLU factorization is implemented 
Understand Cholesky decomposition via  LDL transposed
Know definition of algebraic multiplicity and geometric multiplicity 
Know determinant and trace are related to eigenvalues
Be able to state and prove that every square matrix has a Schur factorization
Know normality is equivalent to unitary diagonalizability and in particular for hermitian matrices
Be able to describe the two stages of eigenvalue algorithms
Be able to describe power iteration via Rayleigh quotient for symmetric matrices
Know the convergence rates for eigenvalue/vector of  power iteration via Rayleigh quotient
Know what Ritz values and Ritz vectors are
Know the polynomial approximation problem associated with Arnoldi method
Know invariance properties of Arnoldi method
Know Ritz values from Arnoldi iteration are related to ``extreme eigenvalues 
Know the polynomial approximation problem associated with GMRES
Know invariance and convergence properties of GMRES (monotone decrease in error, faster convergence from eigenvalue clustering) 
Be able to state the steepest descent algorithm
Be able to state the residual norm related to the minimizing polynomial  
Understand residuals in CG are orthogonal and search directions are $A$-conjugate  
Know monotonic convergence of CG   
Be able to state the finite termination property of CG  
Know the polynomial approximation problem associated with CG
Be able to state the  PCG algorithm

(Useful to know)

Know matrix inverse times vector as a change of basis operation
Know orthogonal vectors are linearly independent
Know definition of weighted vector norms and corresponding induced matrix norms
Know different definitions of Frobenius norm
Know positive singular values are distinct and singular vectors are unique up to complex signs 
Know relation between null space of a projector and the range space of its complementary projector 
Understand what machine epsilon is
Know uniqueness of QR factorization
Understand why one of the two Householder reflectors is a better choice
Be able to solve $Ax=b$ for   square $A$ with a known QR factorization 
Know how to calculate the relative condition number of a general problem
Know how to determine stability and backward stability for simple problems
Know that QR factorization via Householder factorization is backward stable
Understand the difference between stability and accuracy
Know number of operation for LU factorization is   O (n^3) 
Know number of operation for pivoting is  O (n^2) 
Know how pivots are chosen in complete pivoting
 Know how Cholesky decomposition is implemented 
Know algebraic multiplicity is $\geq$ geometric multiplicity
Know  defective eigenvalues and matrices 
State operation count for reduction to upper Hessenberg form
Know the convergence rates for eigenvalue/vector of  inverse iteration 
Understand the meaning of cubic convergence
Be able to describe simultaneous iteration
Know convergence of QR  
Understand loss of orthogonality in Lanczos may cause computational problem
Know bound for error of CG  
Be able to state the error bound of CG  
Know how preconditioning works (both Hermitian and non-Hermitian cases)
Construct (block) diagonal, incomplete LU and incomplete Cholesky preconditioners

(Nice to know)

Know proof of existence and uniqueness of SVD 
Know oblique projector
Know the proof of  characterization of orthogonal projector 
Know the operation count of Gram-Schmidt iterations
Know the operation count of Householder QR factorization
Know a projector separate tensor product of complex plane into two spaces
Know that solution of $Ax=b$  via QR is of order condition number time machine epsilon 
Know that back substitution is backward stable 
Be able to derive the conditioning bounds for a least squares problem when the matrix $A$ is perturbed. 
Stability of Gaussian Elimination
Know what a growth factor is 
Know linear solve via Cholesky decomposition is stable
Stability of reduction to Hessenberg form
Know QR algorithm is backward stable
Know Strassen's formula
Know Arnoldi lemniscates
Know physical interpretation of Lanczos iteration and electric charge distribution
CGN and BCG and other Krylov space methods   [important topics but you will not be tested on these]

Textbooks

Possible textbooks for this course include (but are not limited to):

Lloyd N. Trefethen and David Bau III, Numerical Linear Algebra, SIAM; 1997; ISBN: 0898713617, 978-0898713619

James W. Demmel, Applied Numerical Linear Algebra, SIAM; 1997; ISBN: 0898713897, 978-0898713893

Gene H. Golub and Charles F. Van Loan, Matrix Computations, 3rd Ed., Johns Hopkins University Press, 1996; ISBN: 0801854148, 978-0801854149

William L. Briggs, Van Emden Henson and Steve F. McCormick, A Multigrid Tutorial, 2nd Ed., SIAM, 2000; ISBN: 0898714621, 978-0898714623

Barry Smith, Petter Bjorstad, William Gropp, Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations, Cambridge University Press, 2004; ISBN: 0521602866, 978-0521602860

Courses for which this course is prerequisite

Math 343, 410; or equivalents.