Communication-Avoiding Linear Algebra
Mark Frederick Hoemmen, Marghoob Mohiyuddin, Laura Grigori1, James Demmel, Katherine A. Yelick, Olga Holtz2, Grey Ballard, Oded Schwartz3, Hua Xiang4 and Hua Xiang5
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