CME 324/CS 336. Advanced Methods in Matrix Computations:
Iterative Methods
Institute for Computational and Mathematical Engineering
and the Department of Computer Science
Stanford University
Spring 2006
This is a course on Matrix Computations with emphasis on iterative
methods for solving linear systems. The course will include such methods
as the Conjugate Gradient Method and GMRES. There will be some discussion
of eigenvalue methods too. Prerequisite: CME 302/CS 237A. Numerical Linear
Algebra.
Announcements
- 05/17/06: Instructions for term paper have been posted.
- 05/21/06: There will not be a lecture on Friday, May 26.
- 05/16/06: Problem 3 added to Problem Set 2. Please see updated
file below.
- 05/11/06: Problem Set 2 has been posted.
- 05/10/06: There will be lectures on the following Fridays: May 12, 19
& 26. The last day of class is May 26.
- 04/19/06: Problem Set 1 has been posted.
- 04/10/06: Future classes will be held in Gates 100 instead of Gates
260.
- 04/06/06: Please send Lek-Heng an e-mail if you are not registered
for the class but want your e-mail to be included in the class mailing
list.
- 04/05/06: There will be no Friday lectures unless announced
otherwise.
Lectures
Location: Gates Building, Room 100
Times: 11:00 AM–12:15 PM on Mon/Wed
Course staff
Instructor: Gene
Golub (golub@stanford.edu).
Gates Building 2B, Room 280
(650) 723-3124
Office hours by appointment.
Teaching assistant: Lek-Heng Lim (lekheng@stanford.edu).
Gates Building 2B, Room 286
(650) 723-4101
Office hours by appointment.
Topics
- Introduction
- Sparse and structured matrices
- Model problem: Poisson equation
- Stationary Methods
- SOR: Successive overrelaxation
- SSOR: Symmetric SOR
- Property A
- Checkerboard/red-black ordering
- Block methods
- Chebyshev polynomials
- Lebedev-Finogenov parameter ordering
- Regular splitting
- Ostrowski theorem
- Splitting and preconditioning
- Chebyshev semi-iterative method
- Chebyshev accleration and CG
- Forsythe-Straus theorem
- Fast Poisson solver
- Domain decomposition
- Incomplete factorization
- Banded and block-tridiagonal matrices
- M matrix
- Meijerink-van der Vorst theorem
- KKT systems
- Real positive matrices
- Additive polar decomposition
- Cayley transform
- Complex symmetric matrices
- Arrow-Hurwitz-Uzawa algorithm
- Krylov Subspace Methods
- Steepest descent
- Kantorovich inequality
- CG: conjugate gradient method
- Preconditioned CG from Chebyshev acceleration
- Classical CG method
- Lanczos tridiagonalization
- Unsymmetric and singular systems
- Least squares problems
- Golub-Kahan bidiagonalization
- Paige-Saunders LSQR
- Saad-Schultz GMRES: generalized minimal residual
- Unsymmetric Lanczos tridiagonalization
- BiCG method
- Parlett's look-ahead strategies
- Freund-Nachtigal QMR: quasi-minimal residual
- Other Topics
- Moments
- Quadrature: Gauss, Gauss-Radau, Gauss-Lobatto
- Stieljes integrals
- Orthogonal polynomials
- Estimating values of bilinear forms of analytic
functions of symmetric matrices
Lecture notes, etc
- Lecture 10 (05/08/06):
-
Transcript (posted: 05/10/06)
-
G.H. Golub, "Matrices, moments, and quadrature with
applications," Symposium Optim. Data Anal., September
21–23, 2005, Canberra, Australia.
-
G.H. Golub, "Matrix computation and the theory of
moments," Bull. Belg. Math. Soc. Simon Stevin,
suppl. (1996), pp. 1--9.
-
G.H. Golub and G. Meurant, "Matrices, moments and
quadrature," pp. 105–156 in Numerical analysis 1993,
Pitman Research Notes in Mathematics, 303, Longman, Harlow, UK,
1994.
Term paper
Read a paper or report which discusses some method for solving a linear
system. It can be a well-known method or some new methods, possibly
illustrating a new pre-conditioner. A good place to start is some of our
SCCM
technical reports. If you prefer older papers, check out the
list here.
Gene and Lek-Heng will be pleased to help select if you come by (do not
send e-mail messages to Gene though).
A report of about eight pages is due on Friday, May 26 at 5PM. The
report should have some descriptive material and a summary of numerical
experiments.
- Homework 2: PDF; TeX source: prob2.tex (posted: 05/11/06; updated: 05/16/06; due:
05/24/06)
Grades and assignments
A grade will be assessed based on about three homework problem sets and a
term paper.
Textbooks
- G. Golub and C. Van Loan, Matrix computations, 3rd Ed., Johns
Hopkins Series in the Mathematical Sciences, 3, Johns Hopkins University Press, Baltimore, MD, 1996. ISBN: 0-8018-5414-8
- J.C. Strikwerda, Finite difference schemes and partial
differential equations, 2nd Ed., SIAM, Philadelphia, PA, 2004.
ISBN: 0-89871-567-9
- H.A. van der Vorst, Iterative Krylov methods for large linear
systems,
Cambridge Monographs on Applied and Computational Mathematics, 13
Cambridge University Press, Cambridge, UK, 2003. ISBN:
0-521-81828-1
- R.S. Varga, Matrix iterative analysis, 2nd Ed., Springer Series in
Computational Mathematics, 27,
Springer-Verlag, Berlin, 2000. ISBN: 3-540-66321-5
Softwares
About this page
You may reach this page through either http://cme324.stanford.edu or http://www.stanford.edu/class/cme324.
Contact: Comments on these pages are welcome. Please write to
lekheng@stanford.edu
