[BANANA] Special Seminar: Oct 19

[Gene H Golub]

Title: The Conjugate Gradient Method with Automatic Preconditioning
Where:  Gates 498
Time: 4:15

Abstract:

Solving a linear system is one of the most 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 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.



++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
I AM HAVING TROUBLE WITH MY MAILER.
PLEASE SEND ALL FUTURE MAIL TO ME AT
golub at stanford.edu.
Thanks. Gene



Gene Golub,  Fletcher Jones Professor of Computer Science
Gates 2B
Computer Science Dept
Stanford University
Stanford, CA 94305
USA

Office Phone: 650 723 3124
Home Phone: 650 323 0105
FAX:  (650) 618 2767
Mobile: 650 796 5402