Avoiding Communication in the Lanczos Bidiagonalization Routine and Associated Least Squares QR Solver
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.
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 12, 2015
- Accession Number
- ADA624905
Entities
People
- Erin Carson
Organizations
- University of California, Berkeley