Accurate conjugate gradient methods for families of shifted systems (Q1826599)

Previous implementations of the multishift conjugate gradient least squares (CGLS) method for solving \((A^TA+\sigma I)x^\sigma = A^Tb\) for different parameters \(\sigma>0\) simultaneously showed in some cases a limited accuracy, due to roundoff errors, which depends on the square of \(\text{cond}(A)\). The authors propose a new implementation which tries to overcome this limitation. The first key of the implementation is the use of coupled recurrences for the construction of an orthogonal basis for the Krylov subspace. This leads to a perturbed Lanczos-type relation where the perturbation has a favorable structure. The second key ingredient is the accurate and efficient construction of the iterates which exploits that a tridiagonal matrix of the Lanczos part is available in factorized form. The paper presents a roundoff error analysis of this approach for the cases \(\sigma = 0\) and \(\sigma\to\infty\). Numerical tests show that the proposed implementation leads to more accurate results in cases where previous implementations failed. The accuracy of the new multishift CGLS implementation is comparable to the accuracy of the CGLS method which solves the systems for each \(\sigma\) separately.