Title:
Accurate conjugate gradient methods for families of shifted systems
Abstract:
We consider the solution of the linear system
\[
(\B.A^{\t.T} \B.A + \sigma \B.I) {\B.x}^{\sigma} = \B.A^{\t.T} \B.b,
\]
for various real values of $\sigma$. This family of shifted systems
arises, for example, in Tikhonov regularization and computations in
lattice quantum chromodynamics. For each single shift $\sigma$ this
system can be solved using the conjugate gradient method for least
squares problems (CGLS). In literature various implementations of the,
so-called, multishift CGLS methods have been proposed. These methods
are mathematically equivalent to applying the CGLS method to each
shifted system separately but they solve all systems simultaneously and
require only two matrix-vector products (one by $\B.A$ and one by
$\B.A^{\t.T}$) and two inner products per iteration step.
Unfortunately, numerical experiments show that, due to roundoff errors,
in some cases these implementations of the multishift CGLS method can
only attain an accuracy that depends on the square of condition number
of the matrix $\B.A$. In this talk we will argue that, in the
multishift CGLS method, the impact on the attainable accuracy of
rounding errors in the Lanczos part of the method is independent of the
effect of roundoff errors made in the construction of the iterates. By
making suitable design choices for both parts, we derive a new (and
efficient) implementation that tries to remove the limitation of
previous proposals. A partial roundoff error analysis and various
numerical experiments show promising results.
This is joint work with Jasper van den Eshof