Enlarged Krylov Subspace Methods and Preconditioners for Reducing Communication
Intervenant(s) : Sophie Moufawad (IFPEN)
The performance of an algorithm on any architecture depends on the processing units speed for performing floating point operations (flops) and the speed of accessing the different levels of memory hierarchy. As the cost of communication, or data movement, is much higher than arithmetic operations, and since this gap is expected to continue to increase exponentially, communication is often the bottleneck in numerical algorithms. We are interested in solving systems of linear equations (Ax=b) using iterative methods such the Krylov Subspace methods. In a quest to address the communication problem, recent research has focused on communication avoiding Krylov subspace methods based on the so called s-step methods. However there are very few communication avoiding preconditioners, and this represents a serious limitation for these methods.
We present a communication avoiding ILU0 preconditioner for solving large systems of linear equations (Ax=b) by using iterative Krylov subspace methods. Our preconditioner allows to perform s iterations of the iterative method without communication, by applying a heuristic alternating min-max layers reordering to the input matrix A, and through ghosting some of the input data and performing redundant computation. We also introduce a new approach for reducing communication in the Krylov subspace methods, that consists of enlarging the Krylov subspace by a maximum of t vectors per iteration, based on the domain decomposition of the graph of A. The enlarged Krylov projection subspace methods lead to faster convergence in terms of iterations and to parallelizable algorithms with less communication, with respect to Krylov methods. We present several new Conjugate Gradient methods, such as the multiple search direction with orthogonalization CG (MSDO-CG), long recurrence enlarged CG (LRE-CG), and the short recurrence enlarged CG versions (SRE-CG, SRE-CG2, truncated SRE-CG2).
Marc.Mezzarobba (at) nulllip6.fr