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.)