Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

   

2010 Research Summary

Communication-Avoiding Linear Algebra

View Current Project Information

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.

1INRIA
2UC Berkeley Mathematics
3TU Berlin
4INRIA
5INRIA