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 language | English |
---|---|
Title of host publication | Proceedings of the Cornelius Lanczos International Centenary Conference |
Editors | J. Brown, M. Chu, D. Ellison, R. Plemmons |
Number of pages | 3 |
Publisher | SIAM |
Publication date | 01.06.1994 |
Pages | 288-290 |
Publication status | Published - 01.06.1994 |