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},
    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