Focus on a joint research project: COALA

COALA (2010-2015)

Communication optimal algorithms for linear algebra 

Principal Investigators :

  • Dr. Laura Grigori, ALPINES project-team, Inria ParisRocquencourt
  • Prof. James Demmel, University of California Berkeley

Research objectives:

COALA focuses on the design and implementation of numerical algorithms for today’s large supercomputers formed by thousands of multicore processors, possibly with accelerators. COALA focuses on operations that are at the heart of many scientific applications such as solving linear systems of equations or least squares problems. The algorithms belong to a new class referred to as communication avoiding that provably minimize communication, where communication means the data transferred between levels of memory hierarchy or between processors in a parallel computer. This research is motivated by studies showing that communication costs can already exceed arithmetic costs by orders of magnitude, and that the gap is growing exponentially over time.

Scientific achievements:

COALA has developed communication avoiding algorithms for several operations in linear algebra, such as LU factorization, QR factorization, rank revealing QR factorization, sparse matrix multiplication, iterative solvers, and ILU preconditioner. An important aspect that is considered is the validation of the algorithms in real applications through the team’s collaboration. Several invited plenary talks have been given on this topic at major conferences such as Supercomputing, SIAM Conference on Parallel Processing.

Publications and Awards:

  • 5 Journal articles & 4 Conference papers.
  • The algorithms are progressively implemented in widely used libraries such as LAPACK, ScaLAPACK, and some of them are available in vendor libraries such as Cray’s libsci or Intel’s MKL libraries.

Selected publication:

J. Demmel, L. Grigori, M. Hoemmen, and J. Langou, Communication-optimal parallel and sequential QR and LU factorizations, SIAM Journal on Scientific Computing, Vol. 34, No 1, 2012.

Follow up:

The collaboration have continued with Dr. L. Grigori’s sabbatical at UC Berkeley. The focus of the collaboration extends now to linear algebra operations that are used in Data Analytics and their implementation by using Spark.

More about COALA: