The construction of an algebraically reduced system for the acceleration of preconditioned conjugate gradients
type: Item
instance of: scholarly article
title: The construction of an algebraically reduced system for the acceleration of preconditioned conjugate gradients
zbMATH Open document ID: 0861.65027
DOI: 10.1016/0377-0427(95)00204-9
author: Stanislav S. Bielawski
author: Stepan G. Mulyarchik
author: A. V. Popov
published in: Journal of Computational and Applied Mathematics
publication date: 1996-10-13T00:00:00Z
review text: The preconditioned conjugate gradient method to solve an \(n\)-dimensional symmetric positive definite system \(Ax=b\) is discussed. For the solution, one chooses a \(k\)-dimensional subspace \(S\), generated by the \(A\)-conjugate vectors \(p_0,p_1,\dots,p_{k-1}\). Then the solution \(x\) is split as \(x=y+z\) with \(y\) the \(A\)-projection of \(x\) onto \(S:y=Px\), and \(z\) its \(A\)-orthogonal complement \(z=Rx=(I-P)x\). Then \(z\) is computed by solving iteratively \(Az= R^Tb\), which is equivalent with \(R^TAx=R^Tb\). Usually this iteration will converge faster than the original one on \(x\). The method is traditionally applied to a system that is the cyclic reduction of a discretized selfadjoint partial differential equation. In this paper, an alternative is proposed for this classical use of the method. The success of the method will indeed depend upon the ease of computation of the projection \(y\). This can be made easy by a clever choice of the generating vectors \(p_1,p_2,\dots,p_{k-1}\). This method is illustrated for a system that is a preconditioned cyclically reduced system. The technique corresponds to repeated cyclic reduction by carefully choosing the basis vectors. However, the principles are applicable for any positive definite system.
reviewed by: Adhemar Bultheel
Mathematics Subject Classification ID: 65F10
Mathematics Subject Classification ID: 65F35
Mathematics Subject Classification ID: 65N22
Mathematics Subject Classification ID: 35J25
zbMATH DE Number: 908438
zbMATH Keywords: iterative method
zbMATH Keywords: convergence acceleration
zbMATH Keywords: projection operator
zbMATH Keywords: preconditioned conjugate gradient method
zbMATH Keywords: cyclic reduction
zbMATH Keywords: cyclically reduced system
MaRDI profile type: Publication
full work available at URL: 0377-0427(95)00204-9
OpenAlex ID: W1963925737
cites work: A class of iterative methods for finite element equations
cites work: On the use of preconditioned conjugate gradient methods for red-black ordered five-point difference schemes
cites work: Q3198795
cites work: An incomplete-factorization preconditioning using repeated red-black ordering
cites work: Numerical solution of nonlinear elliptic partial differential equations by a generalized conjugate gradient method
cites work: Iterative Methods for Cyclically Reduced Non-Self-Adjoint Linear Systems
cites work: Line Iterative Methods for Cyclically Reduced Discrete Convection-Diffusion Problems
cites work: Q3254327
cites work: A class of first order factorization methods
cites work: Q3909906
cites work: On the Conjugate Gradient Solution of the Schur Complement System Obtained from Domain Decomposition
cites work: An Iterative Solution Method for Linear Systems of Which the Coefficient Matrix is a Symmetric M-Matrix
cites work: Efficient computational schemes of the conjugate gradient method for solving linear systems
cites work: Deflation of Conjugate Gradients with Applications to Boundary Value Problems
cites work: Q3200466
Recommended article: A fast algebraic multigrid preconditioned conjugate gradient solver
Recommended article: Structure of the preconditioned system in various preconditioned conjugate gradient squared algorithms
Recommended article: Q4035286
Recommended article: An efficient algebraic multigrid preconditioned conjugate gradient solver.
Recommended article: Restrictively preconditioned conjugate gradient methods for systems of linear equations
Recommended article: An acceleration of preconditioned generalized accelerated over relaxation methods for systems of linear equations
Recommended article: Q3549615
Recommended article: Preconditioned conjugate gradient methods applied to certain symmetric linear systems
Recommended article: Q3314449
Recommended article: Reducing Complexity in Parallel Algebraic Multigrid Preconditioners
description: scientific article; zbMATH DE number 908438