AM194: Iterative Methods

Spring 2005

Handouts   |   Assignments   |   Links   |   Course Info   |   Syllabus

• Instructor: Luke Olson(email)

• Time: AB hour, MW 8:30-9:50am

• Location: Wilson Hall Room 303 (in the main quad)

Projects

Name	Topic	Date

Schedule

Date	Topic	More Information
W-20050126	Introduction/Motivation	Covered motivational material in [1], [2], and a number of other sources
M-20050130	Matrcies, Projections, QR	See Chapter 1 in [2], Chapter 2 in [1], and Lectures 7-10 in [3]
W-20050202	More on Householder and Projections	See Chapter 1 in [2] and [.pdf]
M-20050207	Descretizations	Mostly from [4] and Chapter 3 in [2]
W-20050209	Jacobi, Gauss-Seidel, etc.	Chapter 4 of [2] and in [4]
M-20050214	Richardson's iteration, optimizing the acceleration, convergence theory	Chapter 4 of [2] and in [4]
W-20050223	1-D Projection Methods: steepest decent, minres*, residual norm, etc.	Chapter 5 of [2] and Chapter 3 of [1]
M-20050228	1-D Projection Methods, and Krylov Intro	Chapter 5 of [2]
W-20050302	FOM, IOM, DIOM	Chapter 6 in [2]
M-20050307	GMRES and variants	Chapter 6 in [2]
W-20050309	CG version 1.0 with RC1, RC2	Chapter 6 in [2]
M-20050314	MINRES, Orthomin(j), Orthodir(j)	Chapter 2-3 in [5]
W-20050316	Faber-Manteuffel, Convergence Theory	Chapter 6 in [2]
M-20050321	Lanczos Biorthogonolization	Chapter 7 in [2], Chapter 6-7 in [1], and Chapter 5 in [5]
W-20050323	BiCG, QMR, BiCGSTAB	Chapter 7 in [2]
M-20050328	Spring Break	-
W-20050330	Spring Break	-
M-20050404	Copper	-
W-20050406	Copper	-
M-20050411	Preconditioned Krylov Methods, Right vs. Left Preconditioning	Ch. 9 in [2]
W-20050413	Basic Preconditioning Schemes, ILU	Ch. 7 in [1]
M-20050418	ILU(p), ILUT(p,t)	Ch. 10 in [2]
W-20050420	AINV routines, Domain Decomposition Intro	Ch. 10,14 in [2]
M-20050425	Domain Decomposition	Ch. 14 in [2]
W-20050327	Domain Decomposition and Multigrid	Ch. 14,13 in [2]
M-20050502	Presentations	Narayan, Chun, Qiu
W-20050504	Presentations	Paulsen, Rienne, Wisniewski
M-20050509	Presentations	Schiemenz, Doran, Dekeukelaere
W-20050511	Presentations	Dean, Lamar, Sibley

[1] Iterative Krylov Methods for Large Linear Systems, First Edition, by van der Vorst. Can be found HERE
[2] Iterative Methods for Sparse Linear Systems, First Edition, by Saad. Can be found HERE
[3] Numerical Linear Algebra, by Trefethen.
[4] Multigrid Tutorial, by Briggs, Henson, McCormick. (notes HERE)
[5] Iterative Methods for Solving Linear Systems, by Anne Greenbaum.

Assignments

Assignment	Due Date
#1 [.pdf]	Mon., February 28, 2005
#2 [.pdf]	Wed., March 16, 2005
#3 [.pdf]	Wed., April 11, 2005
#4 [.pdf]	Mon., May 2, 2005
Final Project Presentations	Reading Period

Assignment suggestions:

HW #1

• should be R_{jj} at the end

HW #2

• calculate the difference between successive residuals. two things are important here: general trend and some sort of average (geometric, etc?). some indication of the performance should be noted by considering the size of the residual (in the euclidean norm)
• compute the error in each iteration using "e=u-A\b;"
• compute the min and max eigs with "eigs(A,6,'LM')" and "eigs(A,6,'SM')" for example
• as many of you have noticed, the h is too small for use in matlab. just use a few representative grid sizes to notice a general trend. Keep h=hx=hy.
• to preserve symmetry (for a=b=0) with the directly boundary conditions, do not include the boundary "dof" in the algebraic system. only solve for the interior points.
• use sparse storage in matlab!

HW #3

• Use the Matlab routines to help write your code and to check the result. Don't get as fancy as the matlab routines for homework purposes though.

HW #4 First of all be sure to see me if there are difficulties.

• Use Matlab's GMRES for this one.
• This may be really helpful in generating A (i.e. it does it for you): genA.m
• genA.m uses this: tridiag.m
• Write your own D, GS, and ILU(p) solvers. I would encourage you to use this as a template: ilup.m

Course Info

Summary: Large, sparse systems of equations arise in many areas of mathematical application and in this course we explore the popular numerical solution techniques being used to efficiently solve these problems. Throughout the course we will study preconditioning strategies, Krylov subspace acceleration methods, and other projection methods. In particular, we will develop a working knowledge of the Conjugate Gradient and Minimum Residual (and Generalized Minimum Residual) algorithms. Multigrid and Domain Decomposition Methods will also be studied as well as parallel implementation, if time permits.

Synopsis: The time needed to solve a system of equations is dependent on both the structure and size of the matrix. For many problems, as the system grows in size solving the problem exactly (with a direct method like Gaussian elimination) becomes computationally prohibitive. Thus the need for a numerical approach. Iterative solution techniques are effective if the correct method is chosen and if implemented correctly (see image below).

Course Outline: See the syllabus below...

Course Scope: The intent of an AM194 "Seminar" course is to cover selected special topics. The scope of the course will be broad. A general overview of the field of iterative solution strategies will be presented and certain methods will be covered in detail.

Course Structure: The course will be lecture based. A light load of homework problems will be assigned (biweekly). These will include reading selections and helpful exercises. Much of the homework will be implementation based, requiring a familiarity with Matlab or C/C++, etc. There are no exams, except the "final" exam, which is a project. The final project will include a culmination of the ideas covered during the course and should be related to your own research interests (I will help with topics).

Syllabus

This is the intended outline of topics. More details as the semester unfolds:

• Overview of Matrices (properties and behavior)
• Intro to numerical partial differential equations
• Basic Iterative Methods: Jacobi, Gauss-Seidel, SOR, block routines
• Projection Methods
• Krylov Methods: GMRES, MINRES, CG, BICGSTAB
• Preconditioning: ILU, SPAI, etc.
• Other: Multigrid Methods (time permitting)

Helpful Links

Saad's first edition.

Templates Book: The well-known online book.

Notes: Some great notes on iterative methods by Henk van der Vorst.

MGNET: Repository and info page for the multigrid research community.

Matlab: Much of the programming can be accomplished using Matlab. It is particularly useful for testing algorithms. Of course, you can do the assignments in C/C++, FORTRAN, or others as well.

MathSciNet: From Brown, you should have access to the AMS paper database.