Department of Mathematics Syllabus

This syllabus is advisory only. For details on a particular instructor's syllabus (including books), consult the instructor's course page. For a list of what courses are being taught each quarter, refer to the Courses page.

MAT 226B: Numerical Methods: Large-Scale Matrix Computations
Approved: 2008-06-01, Roland Freund

Units/Lecture:

Winter, alt years; 1st LEC 3.0 hrs/wk; 2nd T-D 1.0 hrs/wk

Suggested Textbook: (actual textbook varies by instructor; check your instructor)

Prerequisites:

167 or equivalent, or consent of instructor; familiarity with some programming language.

Course Description:

Numerical methods for large-scale matrix computations, including direct and iterative methods for the solution of linear systems, the computation of eigenvalues and singular values, the solution of least-squares problems, matrix compression, methods for the solution of linear programs.

Suggested Schedule:

- Direct Methods for the Solution of Linear Systems
          o Sparse Cholesky factorization
          o Sparse LU factorization
          o Fast elliptic solvers
- Iterative Methods for the Solution of Linear Systems
          o Krylov subspace methods for symmetric systems
          o Krylov subspace methods for nonsymmetric systems
          o Preconditioning
          o Multigrid methods
- Eigenvalue and Singular Value Problems
          o The power method
          o Krylov subspace methods
          o Applications in information retrieval
          o Applications in image processing
- Solution of Least-Squares Problems
          o Sparse QR factorization
- Matrix Compression of Low-Rank Matrices
          o Randomized algorithms
          o FMM/HSS algorithm
- Linear Programming
          o Simplex method
          o Interior-point methods

Additional Notes:

No required textbook. Optional references:
  • G.H. Golub and C.F.Van Loan, Matrix Computations, 3rd Ed., Johns Hopkins University Press, 1996
  • Y. Saad, Iterative Methods for Sparse Linear Systems, SIAM, 2003
  • T.A. Davis, Direct Methods for Sparse Linear Systems, SIAM, 2006
A few topics of this proposed course are also covered in ECS 231 (Large-Scale Scientific Computation), but the focus in ECS 231 is on applications and software related aspects of these topics. The focus of this course, however, is on a rigorous mathematical treatment of these topics. Therefore, the potential overlap of ECS 231 and this proposed course is minimal.

Assessment:

Homework assignments, covering both theory and computational problems: 50%. Final project and report: 50%