Location: Science Conference Room / Main Campus, Zouk Mosbeh
Time: 3:00 p.m.
In this work, we are interested in solving systems of linear equations (Ax=b) using the Krylov Subspace iterative methods. When implementing such methods on modern High Performance Computers (HPC), one must take into account the fact that the cost of communication, or data movement between computer memory (memories) and processing unit(s), is much higher than the cost of arithmetic operations (processing time). We present our recent results related to “communication avoiding” Krylov subspace methods (L. Grigori and S. Moufawad (2015), SIAM Journal on Scientific Computing, 37(2), C217–C246). These methods, are based on the so called “s-step Krylov methods” that merge s iterations of the classical Krylov methods, by restructuring the algorithms, where at iteration k, x_{ks} is computed from x_{(k-1)s}. In practice, appropriate preconditioners for systems of linear equations are usually selected to accelerate the convergence of the Krylov method. As the choice of the preconditioner must also be “communication avoiding”, we present an ILU0 preconditioner that allows the computation of s matrix-vector multiplications of the form (LU)^{-1}Ax without communication. Such goal is achieved by applying the new alternating min-max layers (AMML) reordering, which reorders the rows and columns of the input matrix A. With such reordering, it is possible to perform the ILU0 factorization and the matrix-vector multiplications in parallel, and without communication by “ghosting” some of the input data and performing redundant computations. Theoretical and experimental results will be discussed.
The speaker at this seminar will be Dr. Sophie Moufawad (AUB).