Math 510: Numerical Methods for Linear Algebra
Contents
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 and practical definitions and properties of norms Know definition and properties of SVD Know definitions of and properties of 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 QR factorization Know how least squares problems arise from a polynomial fitting problem Know how to solve least square problems using
(1) normal equations/pseudoinverse, (2) QR factorization and (3) SVD
Be able to define the condition of a problem and related condition number Know how to calculate the condition number of a matrix 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 Be able to apply the fundamental axiom of floating point arithmetic to determine stability Know the difference between stability and conditioning Know the four condition numbers of a least squares problem Know how to construct LU and PLU factorizations Know how PLU is related to Gaussian elimination Understand Cholesky decomposition Know properties of eigenvalues and eigenvectors under similarity transformation and shift Know various matrix decomposition related to eigenvalue calculation:
(1) spectral decomposition (2) unitary diagonaliation (2) Schur decomposition
Understand why and how matrices can be reduced to Hessenberg form Know various form of power method and what Rayleigh quotient iteration and their properties and convergence rates Know the QR algorithm with shifts Understand simultaneous iteration and QR algorithm are mathematically equivalent Understand the Arnoldi algorithm and its properties Know the polynomial approximation problem associated with Arnoldi method Be able to state the GMRES algorithm Be able to state three term recurrence of Lanczos iteration for real symmetric matrices Understand the CG algorithm and its properties Know the v-cycle multigrid algorithm and the full multigrid algorithm Know how to construct preconditioners: (block) diagonal, incomplete LU and incomplete Cholesky preconditioners Know CGN and BCG and other Krylov space methods
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
Additional topics
Multigrid method; Domain decomposition method; Freely available linear algebra software; Fast multipole method for linear systems; Parallel processing
Courses for which this course is prerequisite
Math 343, 410; or equivalents.
