Efficient and stable minimal residual methods for complex symmetric linear systems and least squares problems with multiple right-hand sides
Rasmus Munk LarsenSCCM, Stanford University
Monday July 3, 2000, 2.00 pm CERFACS Conference Room
Abstract :
We derive stable implementations of minimal residual methods for problems with multiple right-hand sides. For Galerkin-type methods like CG or CGLS it is relatively straightforward to implement the Galerkin projection step. However, in (quasi-) minimal residual methods like CSYM, MINRES, QMR or LSQR an explicit deflation of the residuals has to be added to make the method stable in finite precision arithmetic. We show that this can be implemented cheaply by adding two extra simple recurrences. In addition, this technique gives rise to variants of the original algorithms where the numerical stability does not depend critically on choosing the right-hand side as starting vector in the underlying Lanczos process.
We discuss several algorithmic variants for complex symmetric problems with multiple right-hand-sides that arise, e.g., in electromagnetics. In particular we illustrate stable ways of adding the Galerkin projection step to
a) complex symmetric QMR and BiCG based on the non-symmetric Lanczos process
and
b) CSYM and an algorithm we call CCG (and that we believe is new), which are minimum-residual and Galerkin-type algorithms based on the complex symmetric Lanczos process.
The technique can also be applied to derive variants of MINRES and LSQR for multiple right-hand sides. These algorithms will be particularly useful in computing regularized solutions for discrete ill-posed problems.
Cerfacs' Conferences 1999-2001 Home Page
