Math 510: Numerical Methods for Linear Algebra
Numerical Methods for Linear Algebra.
Math 314, CS 142; or equivalent.
Numerical matrix algebra, orthogonalization and least squares methods, unsymmetric and symmetric eigenvalue problems, iterative methods, advanced solvers for partial differential equations.
Desired Learning Outcomes
This course is designed to prepare students to solve linear algebra problems arising from many applications such as mathematical models of physical or engineering processes. Students are introduced to modern concepts and methodologies in numerical linear algebra, with particular emphasis on t methods that can be used to solve very large scale problems. In depth discussion of theoretical aspects such as stability and convergence will be used to enhance the students' understanding of the numerical methods. Students will also be required to perform some programming and computation so as to gain experience in implementing and observing the numerical performance of the various numerical methods.
The course addresses the University goal of developing the skills of sound thinking, effective communication and quantitative reasoning. The course also allow students, especially undergraduate students, to develop some depth and consequently competence in an important area of applied mathematics.
This course requires knowledge of higher level courses in mathematics. The course also serves as an introductory graduate level course to prepare the students to apply the methods learned in their research projects.
Mastery of materials in an undergraduate course in linear algebra. Knowledge of matlab.
Minimal learning outcomes
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 bounds
Know 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
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
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.