Volume 47, pp. 206-230, 2017.

Varying the s in your s-step GMRES

David Imberti and Jocelyne Erhel

Abstract

Krylov subspace methods are commonly used iterative methods for solving large sparse linear systems. However, they suffer from communication bottlenecks on parallel computers. Therefore, $s$-step methods have been developed, where the Krylov subspace is built block by block so that $s$ matrix-vector multiplications can be done before orthonormalizing the block. Then Communication-Avoiding algorithms can be used for both kernels. This paper introduces a new variation on the $s$-step GMRES method in order to reduce the number of iterations necessary to ensure convergence with a small overhead in the number of communications. Namely, we develop an $s$-step GMRES algorithm, where the block size is variable and increases gradually. Our numerical experiments show a good agreement with our analysis of condition numbers and demonstrate the efficiency of our variable $s$-step approach.

Full Text (PDF) [723 KB], BibTeX

Key words

Communication-Avoiding, $s$-step Krylov subspace method, GMRES algorithm, variable $s$-step

AMS subject classifications

65F10, 65N22

Links to the cited ETNA articles

[13]	Vol. 3 (1995), pp. 160-176 Jocelyne Erhel: A parallel GMRES version for general sparse matrices
[27]	Vol. 40 (2013), pp. 381-406 Desire Nuentsa Wakam and Jocelyne Erhel: Parallelism and robustness in GMRES with a Newton basis and deflated restarting