Accuracy of the s-step Lanczos method for the symmetric eigenproblem

Erin Carson and James Demmel

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2014-165
September 17, 2014

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2014/EECS-2014-165.pdf

The $s$-step Lanczos method is an attractive alternative to the classical Lanczos method as it enables an $O(s)$ reduction in data movement over a fixed number of iterations. This can significantly improve performance on modern computers. In order for $s$-step methods to be widely adopted, it is important to better understand their error properties. Although the $s$-step Lanczos method is equivalent to the classical Lanczos method in exact arithmetic, empirical observations demonstrate that it can behave quite differently in finite precision.

In this paper, we demonstrate that bounds on accuracy for the finite precision Lanczos method given by Paige [\emph{Lin. Alg. Appl.}, 34:235--258, 1980] can be extended to the $s$-step Lanczos case assuming a bound on the condition numbers of the computed $s$-step bases. Our results confirm theoretically what is well-known empirically: the conditioning of the Krylov bases plays a large role in determining finite precision behavior. In particular, if one can guarantee that the basis condition number is not too large throughout the iterations, the accuracy and convergence of eigenvalues in the $s$-step Lanczos method should be similar to those of classical Lanczos. This indicates that, under certain restrictions, the $s$-step Lanczos method can be made suitable for use in many practical cases.


BibTeX citation:

@techreport{Carson:EECS-2014-165,
    Author = {Carson, Erin and Demmel, James},
    Title = {Accuracy of the s-step Lanczos method for the symmetric eigenproblem},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2014},
    Month = {Sep},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2014/EECS-2014-165.html},
    Number = {UCB/EECS-2014-165},
    Abstract = {The $s$-step Lanczos method is an attractive alternative to the classical Lanczos method as it enables an $O(s)$ reduction in data movement over a fixed number of iterations. This can significantly improve performance on modern computers. In order for $s$-step methods to be widely adopted, it is important to better understand their error properties. Although the $s$-step Lanczos method is equivalent to the classical Lanczos method in exact arithmetic, empirical observations demonstrate that it can behave quite differently in finite precision.  

In this paper, we demonstrate that bounds on accuracy for the finite precision Lanczos method given by Paige [\emph{Lin. Alg. Appl.}, 34:235--258, 1980] can be extended to the $s$-step Lanczos case assuming a bound on the condition numbers of the computed $s$-step bases. Our results confirm theoretically what is well-known empirically: the conditioning of the Krylov bases plays a large role in determining finite precision behavior. In particular, if one can guarantee that the basis condition number is not too large throughout the iterations, the accuracy and convergence of eigenvalues in the $s$-step Lanczos method should be similar to those of classical Lanczos. This indicates that, under certain restrictions, the $s$-step Lanczos method can be made suitable for use in many practical cases.}
}

EndNote citation:

%0 Report
%A Carson, Erin
%A Demmel, James
%T Accuracy of the s-step Lanczos method for the symmetric eigenproblem
%I EECS Department, University of California, Berkeley
%D 2014
%8 September 17
%@ UCB/EECS-2014-165
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2014/EECS-2014-165.html
%F Carson:EECS-2014-165