On the efficient implementation of preconditioned s-step conjugate gradient methods on multiprocessors with memory hierarchy
type: Item
instance of: scholarly article
title: On the efficient implementation of preconditioned s-step conjugate gradient methods on multiprocessors with memory hierarchy
zbMATH Open document ID: 0679.65020
DOI: 10.1016/0167-8191(89)90062-8
published in: Parallel Computing
publication date: 1989-01-01T00:00:00Z
review text: The use of the preconditioned conjugate gradient (CG) method in approximating the solution of a sparse symmetric and positive definite linear system of equations \(Ax=f\) is considered. The main goal of the work is to prove that the preconditioned s-CG method can be efficiently implemented so that only one global memory sweep for s-CG iterations is needed. Polynomial and incomplete Cholesky preconditionings are used. The preconditioned CG algorithm consists in applying the CG method to the transformed system \((K^{1/2}AK^{1/2})K^{-1/2}x=K^{1/2}f,\) where K is the preconditioning matrix and is selected as an approximation to the inverse of A. The s-step CG generalizes the CG method and has improved data locality and parallel properties. It can be organized so that only one sweep through the data is needed to complete one step of s-CG which is equivalent to s successive steps of CG. Two manners to choose the matrix K in order to produce efficient theoretical implementation of the preconditioned s-CG are presented. For the incomplete Cholesky preconditioning a completely parallelizable form of the preconditioner is obtained. The authors describe the manner in which different parts of s-CG can be implemented efficiently on vector processor with local memory having a register-to-register or memory-to- memory organization. Some experimental results obtained on the ALLIANT FX/8 multiprocessor system are presented. For some linear systems obtained from the discretization of elliptic PDEs the obtained computational results show that on a multiprocessor system with memory hierarchy the 5-step preconditioned CG is faster than the standard preconditioned CG.
Mathematics Subject Classification ID: 65F10
Mathematics Subject Classification ID: 65N22
Mathematics Subject Classification ID: 65F35
Mathematics Subject Classification ID: 65F50
Mathematics Subject Classification ID: 35J05
zbMATH DE Number: 4113849
zbMATH Keywords: s-step conjugate gradient methods
zbMATH Keywords: parallel algorithms
zbMATH Keywords: numerical examples
zbMATH Keywords: preconditioned conjugate gradient method
zbMATH Keywords: incomplete Cholesky preconditionings
zbMATH Keywords: multiprocessor system
author: Anthony T. Chronopoulos
author: C. William Gear
MaRDI profile type: Publication
full work available at URL: 0167-8191(89)90062-8
OpenAlex ID: W2082007415
description: scientific article; zbMATH DE number 4113849