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:

  1. Data structures
    1. Sparse representations
    2. Algebraic decision diagrams
  2. Direct methods
    1. Sparse Gaussian elimination
    2. Ordering to minimize work: reverse Cuthill-McKee and minimum degree
    3. Stability analysis
  3. Basic iterative methods
    1. Richardson, Jacobi, Gauss-Seidel, SOR
    2. Preconditioning, ILU
    3. Convergence analysis
  4. Gradient methods
    1. Steepest descent, conjugate gradient
    2. convergence analysis
  5. Krylov subspace methods
    1. Arnoldi, Lanczos
    2. GMRES, CGS
  6. Potential applications
    1. Heat diffusion
    2. Image de-noising
    3. Least square linear regression
    4. 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:

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

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