Avoiding communication in the Lanczos bidiagonalization routine and associated Least Squares QR solver

Erin Carson

EECS Department
University of California, Berkeley
Technical Report No. UCB/EECS-2015-15
April 12, 2015

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2015/EECS-2015-15.pdf

Communication -- the movement of data between levels of memory hierarchy or between processors over a network -- is the most expensive operation in terms of both time and energy at all scales of computing. Achieving scalable performance in terms of time and energy thus requires a dramatic shift in the field of algorithmic design. Solvers for sparse linear algebra problems, ubiquitous throughout scientific codes, are often the bottlenecks in application performance due to a low computation/communication ratio. In this paper we develop three potential implementations of communication-avoiding Lanczos bidiagonalization algorithms and discuss their different computational requirements. Based on these new algorithms, we also show how to obtain a communication-avoiding LSQR least squares solver.


BibTeX citation:

@techreport{Carson:EECS-2015-15,
    Author = {Carson, Erin},
    Title = {Avoiding communication in the Lanczos bidiagonalization routine and associated Least Squares QR solver},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {2015},
    Month = {Apr},
    URL = {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2015/EECS-2015-15.html},
    Number = {UCB/EECS-2015-15},
    Abstract = {Communication -- the movement of data between levels of memory hierarchy or between processors over a network -- is the most expensive operation in terms of both time and energy at all scales of computing. Achieving scalable performance in terms of time and energy thus requires a dramatic shift in the field of algorithmic design. Solvers for sparse linear algebra problems, ubiquitous throughout scientific codes, are often the bottlenecks in application performance due to a low computation/communication ratio. In this paper we develop three potential implementations of communication-avoiding Lanczos bidiagonalization algorithms and discuss their different computational requirements. Based on these new algorithms, we also show how to obtain a communication-avoiding LSQR least squares solver.}
}

EndNote citation:

%0 Report
%A Carson, Erin
%T Avoiding communication in the Lanczos bidiagonalization routine and associated Least Squares QR solver
%I EECS Department, University of California, Berkeley
%D 2015
%8 April 12
%@ UCB/EECS-2015-15
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2015/EECS-2015-15.html
%F Carson:EECS-2015-15