@TechReport{ it:2012-001,
author = {Magnus Gustafsson and James Demmel and Sverker Holmgren},
title = {Numerical Evaluation of the Communication-Avoiding
{L}anczos Algorithm},
institution = {Department of Information Technology, Uppsala University},
department = {Division of Scientific Computing},
year = {2012},
number = {2012-001},
month = jan,
abstract = {The Lanczos algorithm is widely used for solving large
sparse symmetric eigenvalue problems when only a few
eigenvalues from the spectrum are needed. Due to sparse
matrix-vector multiplications and frequent synchronization,
the algorithm is communication intensive leading to poor
performance on parallel computers and modern cache-based
processors. The Communication-Avoiding Lanczos algorithm
[Hoemmen; 2010] attempts to improve performance by taking
the equivalence of $s$ steps of the original algorithm at a
time. The scheme is equivalent to the original algorithm in
exact arithmetic but as the value of $s$ grows larger,
numerical roundoff errors are expected to have a greater
impact. In this paper, we investigate the numerical
properties of the Communication-Avoiding Lanczos
(CA-Lanczos) algorithm and how well it works in practical
computations. Apart from the algorithm itself, we have
implemented techniques that are commonly used with the
Lanczos algorithm to improve its numerical performance,
such as semi-orthogonal schemes and restarting. We present
results that show that CA-Lanczos is often as accurate as
the original algorithm. In many cases, if the parameters of
the $s$-step basis are chosen appropriately, the numerical
behaviour of CA-Lanczos is close to the standard algorithm
even though it is somewhat more sensitive to loosing mutual
orthogonality among the basis vectors.}
}