Accuracy of the s-Step Lanczos Method for the Symmetric Eigenproblem in Finite Precision
Lists
Only you see this
Abstract
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.
BibTeX
@article{carson2015accuracy,
author = {Erin C. Carson and James Weldon Demmel},
title = {{Accuracy of the s-Step Lanczos Method for the Symmetric Eigenproblem in Finite Precision}},
journal = {SIAM J. Matrix Anal. Appl.},
year = {2015},
url = {https://openreview.net/forum?id=5uTxh3aMa3a},
}Loading related content...