Enlarged Conjugate Gradient Method for Reducing Communication

Abstract. In this talk, we present enlarged Krylov Conjugate Gradient (ECG) method for reducing communications when solving symmetric positive definite linear systems. This method relies on searching the solution in t directions at each iteration instead of one as in classic Conjugate Gradient. It leads to a faster convergence and thus an important reduction in the number of global communications while increasing arithmetic intensity. Then we propose a method to reduce dynamically the number of search directions constructed at each iteration which is both effective and stable. We present experimental and parallel performance results that show the efficiency of the method.


  • Olivier Tissot, Inria, France, olivier.tissot@inria.fr
  • Laura Grigori, Inria, France, Laura.Grigori@inria.fr