Erin Carson and James Demmel

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2014-55

May 6, 2014

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2014/EECS-2014-55.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 the $s$-step Lanczos method, the computed Lanczos vectors can lose orthogonality at a much quicker rate than the classical method, a property which seems to worsen with increasing $s$.

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 the classical Lanczos method [\emph{IMA J. Appl. Math.}, 18(3):341--349, 1976]. 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. The derived bounds are very similar to those of Paige for classical Lanczos, but with the addition of an amplification term which depends on the condition number of the Krylov bases computed every $s$-steps. Our results confirm theoretically what is well-known empirically: the conditioning of the Krylov bases plays a large role in determining finite precision behavior.

---

BibTeX citation:

@techreport{Carson:EECS-2014-55,
    Author= {Carson, Erin and Demmel, James},
    Title= {Error analysis of the s-step Lanczos method in finite precision},
    Year= {2014},
    Month= {May},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2014/EECS-2014-55.html},
    Number= {UCB/EECS-2014-55},
    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 the $s$-step Lanczos method, the computed Lanczos vectors can lose orthogonality at a much quicker rate than the classical method, a property which seems to worsen with increasing $s$. 

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 the classical Lanczos method [\emph{IMA J. Appl. Math.}, 18(3):341--349, 1976]. 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. The derived bounds are very similar to those of Paige for classical Lanczos, but with the addition of an amplification term which depends on the condition number of the Krylov bases computed every $s$-steps. Our results confirm theoretically what is well-known empirically: the conditioning of the Krylov bases plays a large role in determining finite precision behavior.},
}

EndNote citation:

%0 Report
%A Carson, Erin 
%A Demmel, James 
%T Error analysis of the s-step Lanczos method in finite precision
%I EECS Department, University of California, Berkeley
%D 2014
%8 May 6
%@ UCB/EECS-2014-55
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2014/EECS-2014-55.html
%F Carson:EECS-2014-55