CS472/CM472/CS672 - Goals

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