Difference between revisions of "Math 510: Numerical Methods for Linear Algebra"

Revision as of 13:19, 19 October 2010

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 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

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.