CS472/CM472/CS672 - Fall 2006 Numerical Solution of Large Sparse
Systems of Equations
Instructor: Pascal Poupart
Email: ppoupart [at] cs [dot] uwaterloo [dot] ca
Office Hours: TBA
Lectures: Tuesday & Thursday 4:00-5:20 pm (RCH305)
In many domains, large linear systems must routinely be solved.
instance, in many branches of engineering and physics, partial
differential equations are often approximated by large linear
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
also be paid to stability and convergence issues. Given the wide
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.
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
- 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
It is assumed that each student has completed an introductory course in
numerical computation (i.e., AMATH341, CM271, CS371 or CS370).
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
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.
- 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
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.
- Assignments (4): 50% (12.5% each)
- Final Exam: 50%
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
- Computer Solution of Large Sparse Positive Definite Systems
George and liu
- Iterative solution methods for sparse linear systems
QA188.S17. (Also available on-line)
- Iterative solution methods
- Finite Element Solution of Boundary Value Problems
O. Axelsson and Barker
QA379.A9 (Some intro to CG methods here).