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

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; ...