s-step enlarged Krylov subspace conjugate gradient methods

DOI10.1137/18M1182528zbMATH Open1429.65071arXiv1804.10629MaRDI QIDQ5208740FDOQ5208740

Authors: Sophie Moufawad 

Publication date: 10 January 2020

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Abstract: Recently, enlarged 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, were introduced in the aim of reducing communication when solving systems of linear equations Ax=b. In this paper, the s-step enlarged Krylov subspace Conjugate Gradient methods are introduced, whereby s iterations of the enlarged Conjugate Gradient methods are merged in one iteration. The numerical stability of these s-step methods is studied, and several numerically stable versions are proposed. Similarly to the enlarged Krylov subspace methods, the s-step enlarged Krylov subspace methods have a faster convergence than Krylov methods, in terms of iterations. Moreover, by computing st basis vectors of the enlarged Krylov subspace $mathscr{K}_{k,t}(A,r_0)$ at the beginning of each s-step iteration, communication is further reduced. It is shown in this paper that the introduced methods are parallelizable with less communication, with respect to their corresponding enlarged versions and to Conjugate Gradient.

Full work available at URL: https://arxiv.org/abs/1804.10629

Recommendations

• Enlarged Krylov subspace conjugate gradient methods for reducing communication
• Scalable linear solvers based on enlarged Krylov subspaces with dynamic reduction of search directions
• The adaptive \(s\)-step conjugate gradient method
• s-step iterative methods for symmetric linear systems
• Varying the \(s\) in your \(s\)-step GMRES

zbMATH Keywords

Krylov subspace methodsiterative methodslinear algebrahigh performance computingminimizing communication

Mathematics Subject Classification ID

Parallel numerical computation (65Y05) Preconditioners for iterative methods (65F08) Iterative numerical methods for linear systems (65F10)

Cites Work

• New development in freefem++
• GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
• Methods of conjugate gradients for solving linear systems
• Bi-CGSTAB: A Fast and Smoothly Converging Variant of Bi-CG for the Solution of Nonsymmetric Linear Systems
• A parallel GMRES version for general sparse matrices
• Title not available (Why is that?)
• The block conjugate gradient algorithm and related methods
• Title not available (Why is that?)
• Deflated and Augmented Krylov Subspace Techniques
• s-step iterative methods for symmetric linear systems
• Multiple search direction conjugate gradient method I: methods and their propositions
• Hiding global communication latency in the GMRES algorithm on massively parallel machines
• Avoiding communication in nonsymmetric Lanczos-based Krylov subspace methods
• Implementation of the GMRES Method Using Householder Transformations
• An Augmented Conjugate Gradient Method for Solving Consecutive Symmetric Positive Definite Linear Systems
• Analysis of Augmented Krylov Subspace Methods
• Numerical stability of orthogonalization methods with a non-standard inner product
• Communication Avoiding ILU0 Preconditioner
• Enlarged Krylov subspace conjugate gradient methods for reducing communication
• An efficient deflation technique for the communication-avoiding conjugate gradient

Cited In (2)

• Developing variable \(s\)-step CGNE and CGNR algorithms for non-symmetric linear systems
• Finding solution of linear systems via new forms of BiCG, BiCGstab and CGS algorithms

Uses Software

• FreeFem++
• METIS

This page was built for publication: s-step enlarged Krylov subspace conjugate gradient methods

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5208740)