Algorithms and Complexity Seminar

Monday, September 18, 2006, 4-5:15pm in 32-G575.

The Conjugate Gradient Method with Automatic Preconditioning

Nick Harvey (MIT CSAIL)

Solving a linear system is one of the most basic and fundamental computational problems. Unfortunately, the basic algorithm that most of us learn (Gaussian Elimination) is often useless in practice due to slow running time or stability issues. Instead, it is more common to use iterative solvers, the simplest ones being steepest descent and conjugate gradient. The snag with iterative solvers is that their performance often depends on the "condition number" of the given system, so it is common to modify the given system by applying a "preconditioner" matrix which reduces the condition number. This raises a key question: given a linear system, how can we find a good preconditioner?

In this work, we develop a variant of conjugate gradient method which *automatically* constructs good preconditioners. The general idea is very simple. We run the conjugate gradient method until it "gets stuck". The fact that it is stuck then implies a way to modify the preconditioner so that the conjugate gradient steps will be "less stuck" in the future.

This talk will be self-contained -- the audience only needs to know basic linear algebra, and how to interpret pictures of algorithms that are stuck.

Joint work with John Dunagan, Microsoft Research.

Host: Madhu Sudan

(The Algorithms and Complexity Seminar series talks are usually held Mondays from 4-5:15pm in 32-G575.)