[BANANA] Linear algebra seminar: 24 Jan first talk

[Mark Hoemmen]

Greetings!

The first meeting of the UC Berkeley linear algebra (LAPACK) seminar
will be next Wednesday (24 Jan), in 380 Soda Hall at 11am.  Sou-Cheng
Choi (Stanford Computer Science) will be speaking on "MINRES-QLP: A
Krylov Subspace Method for Singular Symmetric Linear
Equations and Least-Squares Problems."  Here is the abstract:

CG, MINRES, and SYMMLQ are Krylov subspace methods for solving large
symmetric systems of linear equations.  CG (the conjugate-gradient
method) is reliable on positive-definite systems, while MINRES and
SYMMLQ are designed for indefinite systems. When these methods are
applied to an inconsistent system (that is, a singular symmetric
least-squares problem), CG could break down and SYMMLQ's solution
could explode, while MINRES would give a least-squares solution but
not necessarily the minimum-length solution (often called the
pseudoinverse solution). This understanding motivates us to design a
MINRES-like algorithm to compute minimum-length solutions to singular
symmetric systems.

MINRES uses QR factors of the tridiagonal matrix from the Lanczos
process.  Our algorithm uses a QLP decomposition (where rotations on
the right reduce each upper-tridiagonal $R_k$ to a lower-tridiagonal
$L_k$), and so we call it MINRES-QLP. We derive preconditioned
MINRES-QLP, new stopping rules, and short-recurrence estimates of the
solution and residual norms, the matrix norm, and the condition
number.  MINRES-QLP needs one more work-vector than MINRES and about
25% more flops.

The behavior of MINRES and MINRES-QLP is very similar on
well-conditioned linear systems.  We describe how to start with MINRES
and transfer to MINRES-QLP only if the estimated condition number is
large.

Experiments show that the new algorithm returns good-quality solutions
for ill-conditioned systems.  The explanation is that a single
triangular system involving $L_k$ induces fewer roundoff errors than
$k$ ill-conditioned systems involving $R_k$.

This is joint work with Professors Michael Saunders and Chris Paige.

---
Just a reminder -- the Linear Algebra (matrix computations and
scientific computing) Seminar is open to all, and is in the UC
Berkeley course catalog, cross-listed under Math 290 Section 3 and CS
298 Section 39.  It meets on Wednesdays from 11am to noon in 380 Soda
Hall.Coordinator is Prof. B.N.Parlett (parlett at math).  The program
will be a mixture of research talks and tutorials.  The tutorials will
provide a partial sequel to Math 221.

mfh