Pipelined, flexible Krylov subspace methods

DOI10.1137/15M1049130zbMATH Open1347.65067arXiv1511.07226OpenAlexW3103743862WikidataQ57858839 ScholiaQ57858839MaRDI QIDQ2818249FDOQ2818249

Authors: P. Sanan, Sascha M. Schnepp, Dave A. May 

Publication date: 7 September 2016

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

Abstract: We present variants of the Conjugate Gradient (CG), Conjugate Residual (CR), and Generalized Minimal Residual (GMRES) methods which are both pipelined and flexible. These allow computation of inner products and norms to be overlapped with operator and nonlinear or nondeterministic preconditioner application.The methods are hence aimed at hiding network latencies and synchronizations which can become computational bottlenecks in Krylov methods on extreme-scale systems or in the strong-scaling limit. The new variants are not arithmetically equivalent to their base flexible Krylov methods, but are chosen to be similarly performant in a realistic use case, the application of strong nonlinear preconditioners to large problems which require many Krylov iterations. We provide scalable implementations of our methods as contributions to the PETSc package and demonstrate their effectiveness with practical examples derived from models of mantle convection and lithospheric dynamics with heterogeneous viscosity structure. These represent challenging problems where multiscale nonlinear preconditioners are required for the current state-of-the-art algorithms, and are hence amenable to acceleration with our new techniques. Large-scale tests are performed in the strong-scaling regime on a contemporary leadership supercomputer, where speedups approaching, and even exceeding $2imes$ can be observed. We conclude by analyzing our new methods with a performance model targeted at future exascale machines.

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

Recommendations

• The numerical stability analysis of pipelined conjugate gradient methods: historical context and methodology
• Hiding global communication latency in the GMRES algorithm on massively parallel machines
• Flexible Inner-Outer Krylov Subspace Methods
• Scalable linear solvers based on enlarged Krylov subspaces with dynamic reduction of search directions
• A Comparison of Preconditioned Nonsymmetric Krylov Methods on a Large-Scale MIMD Machine

zbMATH Keywords

numerical examplesconjugate gradientpreconditioningparallel computingKrylov methodsconjugate residualglobal communicationgeneralized minimal residuallatency hidingPETSc package

Mathematics Subject Classification ID

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

Cites Work

• GMRES: A Generalized Minimal Residual Algorithm for Solving Nonsymmetric Linear Systems
• Methods of conjugate gradients for solving linear systems
• A Restricted Additive Schwarz Preconditioner for General Sparse Linear Systems
• Title not available (Why is that?)
• Variational Iterative Methods for Nonsymmetric Systems of Linear Equations
• Title not available (Why is that?)
• A Flexible Inner-Outer Preconditioned GMRES Algorithm
• Inexact Preconditioned Conjugate Gradient Method with Inner-Outer Iteration
• Iterative Krylov Methods for Large Linear Systems
• s-step iterative methods for symmetric linear systems
• A Black Box Generalized Conjugate Gradient Solver with Inner Iterations and Variable-Step Preconditioning
• Hiding global communication latency in the GMRES algorithm on massively parallel machines
• A generalized conjugate gradient, least square method
• A stabilized finite element method for the Stokes problem based on polynomial pressure projections
• Some History of the Conjugate Gradient and Lanczos Algorithms: 1948–1976
• Comparison of different propagation steps for lattice Boltzmann methods
• Flexible conjugate gradients
• The Conjugate Residual Method for Constrained Minimization Problems
• Title not available (Why is that?)
• NOTES ON THE SOLUTION OF ALGEBRAIC LINEAR SIMULTANEOUS EQUATIONS
• Composing scalable nonlinear algebraic solvers
• Preconditioning
• A scalable, matrix-free multigrid preconditioner for finite element discretizations of heterogeneous Stokes flow
• Pipelined iterative solvers with kernel fusion for graphics processing units
• Accurately measuring overhead, communication time and progression of blocking and nonblocking collective operations at massive scale

Cited In (10)

• Analyzing the effect of local rounding error propagation on the maximal attainable accuracy of the pipelined conjugate gradient method
• Efficient AMG reduction-based preconditioners for structural mechanics
• The numerical stability analysis of pipelined conjugate gradient methods: historical context and methodology
• Blendenpik: Supercharging LAPACK's Least-Squares Solver
• Scalable linear solvers based on enlarged Krylov subspaces with dynamic reduction of search directions
• A multigrid reduction framework for domains with symmetries
• Hiding global communication latency in the GMRES algorithm on massively parallel machines
• On applying deflation and flexible preconditioning to the adaptive simpler GMRES method for Sylvester tensor equations
• GMRES algorithms over 35 years
• Flexible Inner-Outer Krylov Subspace Methods

Uses Software

• PETSc
• DMAPP

This page was built for publication: Pipelined, flexible Krylov subspace methods

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