Communication-Avoiding Linear Algebra
Kaushik Datta, Mark Frederick Hoemmen, Marghoob Mohiyuddin, Laura Grigori1, James Demmel, Katherine A. Yelick and Olga Holtz2
National Science Foundation, Department of Energy and ACM/IEEE fellowship
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 many of the kernels exist and have shown significant performance improvements over the usual methods.
2UC Berkeley Mathematics