Skip to Main content Skip to Navigation

Reducing the communication and computational costs of Enlarged Krylov subspaces Conjugate Gradient

Laura Grigori 1 Olivier Tissot 1
1 ALPINES - Algorithms and parallel tools for integrated numerical simulations
LJLL - Laboratoire Jacques-Louis Lions, INSMI - Institut National des Sciences Mathématiques et de leurs Interactions, Inria de Paris
Abstract : In this paper we propose an algebraic method in order to reduce dynamically the number of search directions during block Conjugate Gradient iterations. Indeed, by monitoring the rank of the optimal step α k it is possible to detect inexact breakdowns and remove the corresponding search directions. We also propose an algebraic criterion that ensures in theory the equivalence between our method with dynamic reduction of the search directions and the classical block Conjugate Gradient. Numerical experiments show that the method is both stable, the number of iterations with or without reduction is of the same order, and effective, the search space is significantly reduced. We use this approach in the context of enlarged Krylov subspace methods which reduce communication when implemented on large scale machines. The reduction of the number of search directions further reduces the computation cost and the memory usage of those methods.
Complete list of metadata

Cited literature [28 references]  Display  Hide  Download
Contributor : Olivier Tissot Connect in order to contact the contributor
Submitted on : Wednesday, February 1, 2017 - 2:50:37 PM
Last modification on : Wednesday, December 9, 2020 - 3:08:58 PM


Files produced by the author(s)


  • HAL Id : hal-01451199, version 2


Laura Grigori, Olivier Tissot. Reducing the communication and computational costs of Enlarged Krylov subspaces Conjugate Gradient. [Research Report] RR-9023, Inria Paris. 2017. ⟨hal-01451199v2⟩



Record views


Files downloads