ACCURACY OF THE s-STEP LANCZOS METHOD FOR THE SYMMETRIC EIGENPROBLEM IN FINITE PRECISION

摘要

The s-step Lanczos method can achieve an O(s) reduction in data movement over the classical Lanczos method for a fixed number of iterations, allowing the potential for significant speedups on modern computers. However, although the s-step Lanczos method is equivalent to the classical Lanczos method in exact arithmetic, it can behave quite differently in finite precision. Increased roundoff errors can manifest as a loss of accuracy or deterioration of convergence relative to the classical method, reducing the potential performance benefits of the s-step approach. In this paper, we present for the first time a complete rounding error analysis of the s-step Lanczos method. Our methodology is analogous to Paige's rounding error analysis for classical Lanczos [IMA J. Appl. Math., 18 (1976), pp. 341-349]. Our analysis gives upper bounds on the loss of normality of and orthogonality between the computed Lanczos vectors, as well as a recurrence for the loss of orthogonality. We further demonstrate that bounds on accuracy for the finite precision Lanczos method given by Paige [Linear Algebra Appl., 34 (1980), pp. 235-258] can be extended to the s-step Lanczos case assuming a bound on the maximum condition number of the precomputed s-step Krylov bases. Our results confirm that the conditioning of the precomputed Krylov bases plays a large role in determining finite precision behavior. In particular, if one can enforce that the condition numbers of the precomputed s-step Krylov bases are not too large in any iteration, then the finite precision behavior of the s-step Lanczos method will be similar to that of classical Lanczos.