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