Communication-Avoiding Linear Algebra
James Demmel, Katherine A. Yelick, Grey Ballard, Mark Frederick Hoemmen, Marghoob Mohiyuddin, Laura Grigori1, Olga Holtz2, Oded Schwartz3, Hua Xiang4, Andrew Gearhart, Erin Carson, Nicholas Knight and Edgar Solomonik
Microsoft, Intel and Department of Energy
We seek to rearrange all algorithms in numerical linear algebra, both sparse and dense, in order to avoid communication. In the parallel case, that means data movement between processors, and in the sequential case, it means data movement between levels of the memory hierarchy. In the dense case, we have obtained both practical algorithms and theoretical lower bounds for communication in the case of (dense) QR and LU factorization. We are attempting to extend those theoretical bounds, and our remote collaborators are working on practical implementations of the algorithms. In the sparse case, we are currently working on modifying Krylov subspace methods to exploit techniques for avoiding communication when computing sparse matrix-vector products and QR factorizations. Open problems include developing compatible preconditioners and proving stability, as well as the computational challenges of implementing the kernels efficiently. Preliminary implementations of both the sparse and dense kernels exist, and have shown significant performance improvements over the usual methods.
2UC Berkeley Mathematics
More information: http://bebop.cs.berkeley.edu