An Inner Product-free Conjugate Gradient-like Algorithm for Hermitian Positive Definite Systems

Bernd Fischer, Roland Freund

Abstract

The conjugate gradient (CG) algorithm for the solution of Hermitian positive definite linear systems requires the computation of inner products. On modern architectures, inner products often represent a bottleneck, and it is desirable to reduce or even eliminate all the inner products. In this note, an inner product-free CGlike algorithm is presented that simulates the standard CG method by approximating the CG orthogonal polynomials by suitably chosen orthogonal polynomials from the Bernstein-Szego class. 1 Introduction The classical conjugate gradient (CG) algorithm of Hestenes and Stiefel [4] is one of the most widely used iterative methods for the solution of systems of linear equations Ax = b; (1) where A 2 C N ThetaN is Hermitian positive definite. The CG algorithm is a polynomial-based iteration. Given any initial guess x 0 2 C N and setting r 0 = b Gamma Ax 0 , CG generates a sequence of approximations to the solution of (1) of the form x n = x 0 + / n (A)r 0 ; n = 1; ...

Original languageEnglish
Title of host publicationProceedings of the Cornelius Lanczos International Centenary Conference
EditorsJ. Brown, M. Chu, D. Ellison, R. Plemmons
Number of pages3
PublisherSIAM
Publication date01.06.1994
Pages288-290
Publication statusPublished - 01.06.1994

Fingerprint

Dive into the research topics of 'An Inner Product-free Conjugate Gradient-like Algorithm for Hermitian Positive Definite Systems'. Together they form a unique fingerprint.

Cite this