Report 1999-21

Accuracy of Two Three-term and Three Two-term Recurrences for Krylov Space Solvers

M.H. Gutknecht and Z. Strakos

Abstract: It has been widely observed that Krylov space solvers based on two three-term recurrences can give significantly less accurate residuals than mathematically equivalent solvers implemented with three two-term recurrences. In this paper we attempt to clarify and justify this difference theoretically by analyzing the gaps between recursively and explicitly computed residuals. It is shown that, in contrast with the two-term recurrences analyzed by Sleijpen, van der Vorst, and Fokkema (Numer. Algor., 7 (1994), pp. 75--109) and Greenbaum (SIAM J. Matrix Anal. Appl., 18 (1997), pp. 535--551), in the two three-term recurrences the contributions of the local roundoff errors to the analyzed gaps may be dramatically amplified while propagating through the algorithm. This result explains, for example, the well-known behavior of three-term-based versions of the biconjugate gradient method, where large gaps between recursively and explicitly computed residuals are not uncommon. For the conjugate gradient method, however, such a devastating behavior --- although possible --- is not observed frequently in practical computations, and the difference between two-term and three-term implementations is usually moderate or small. This can also be explained by our results.

Keywords: system of linear algebraic equations, iterative method, Krylov space method, conjugate gradient method, three-term recurrence, accuracy, roundoff

Paper: Available as PDF (354 KB) or as hardcopy to order reports@sam.math.ethz.ch.