CS472/CM472/CS672 - Fall 2006 Numerical Solution of Large Sparse
Systems of Equations
Instructor: Pascal Poupart
Email: ppoupart [at] cs [dot] uwaterloo [dot] ca
Website:
http://www.student.cs.uwaterloo.ca/~cs472
Newsgroup: uw.cs.cs472
Office Hours: TBA
Lectures: Tuesday & Thursday 4:00-5:20 pm (RCH305)
Objectives
In many domains, large linear systems must routinely be solved.
For
instance, in many branches of engineering and physics, partial
differential equations are often approximated by large linear
systems;
in machine learning, least square linear regression also leads to large
linear systems; in computational vision, image denoising can also be
formulated as a linear system; in decision-theoretic planning, policy
iteration algorithms for Markov decision processes require the solution
of a series of linear systems.
This course surveys a wide range of numerical techniques to solve large
linear systems. More precisely, the course will focus on data
structures and algorithms that exploit sparsity and redundancy in order
to solve linear systems as large as possible. Special attention
will
also be paid to stability and convergence issues. Given the wide
range
of applications where linear systems arise and the generic nature of
the techniques surveyed, this course should interest all practitioners
from computer science, applied mathematics, computational mathematics,
optimization and engineering.
Outline
The topics we will cover include:
- Data structures
- Sparse representations
- Algebraic decision diagrams
- Direct methods
- Sparse Gaussian elimination
- Ordering to minimize work: reverse Cuthill-McKee and minimum
degree
- Stability analysis
- Basic iterative methods
- Richardson, Jacobi, Gauss-Seidel, SOR
- Preconditioning, ILU
- Convergence analysis
- Gradient methods
- Steepest descent, conjugate gradient
- convergence analysis
- Krylov subspace methods
- Arnoldi, Lanczos
- GMRES, CGS
- Potential applications
- Heat diffusion
- Image de-noising
- Least square linear regression
- Policy iteration for Markov decision processes
Prerequisite:
It is assumed that each student has completed an introductory course in
numerical computation (i.e., AMATH341, CM271, CS371 or CS370).
Course
Organization:
The
course material will be covered primarily in lectures.
You should also read the appropriate sections of the online reference
material for each lecture.
There will be four assignments given in the course. Each
assignment will have a theoretical part and a programming part (C/C++
and Matlab). The approximate out and due
dates
are:
- A1: out Sept 19, due Oct 3
- A2: out Oct 3, due Oct 24
- A3: out Oct 24, due Nov 14
- A4: out Nov 14, due Dec 5
On the due date
of an assignment, the work done to date should be submitted at the
beginning of class; further material may be submitted for half credit
at the start of the next class.
Graduate students registered in CS672 will be required to do additional
questions on the assignments.
There is no midterm. However,
there will also be a final examination of 2.5 hours worth 50% of the
final mark to be
scheduled by the registrar.
Grading Scheme
- Assignments (4): 50% (12.5% each)
- Final Exam: 50%
Reference Material
There is no official textbook for the course. However, the
following books are useful references that contain the algorithms
discussed in class. References to these texts will be made from
time to time.
References Available On-line
Material on Reserve in the library
- Matrix Computations
G. Golub and C. Van Loan
(this is a usefull reference, but I don't recommend you
buy this for this course) QA188.G65x.
- Direct Methods for Sparse Matrices
Duff, Erisman, Reid
QA188.D84.
- Computer Solution of Large Sparse Positive Definite Systems
George and liu
QA188.G46
- Iterative solution methods for sparse linear systems
Y. Saad
QA188.S17. (Also available on-line)
- Iterative solution methods
O. Axelsson
QA297.8.A94
- Finite Element Solution of Boundary Value Problems
O. Axelsson and Barker
QA379.A9 (Some intro to CG methods here).