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
Inria de Paris, INSMI - Institut National des Sciences Mathématiques et de leurs Interactions, LJLL - Laboratoire Jacques-Louis Lions
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 metadatas

Cited literature [28 references]  Display  Hide  Download

https://hal.inria.fr/hal-01451199
Contributor : Olivier Tissot <>
Submitted on : Wednesday, February 1, 2017 - 2:50:37 PM
Last modification on : Friday, September 20, 2019 - 4:34:04 PM

File

RR-9023.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01451199, version 2

Citation

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⟩

Share

Metrics

Record views

805

Files downloads

448