Necessary and Sufficient Conditions for the Existence of a Conjugate Gradient Method

Abstract

We characterize the class $CG(s)$ of matrices A for which the linear system $A{\bf x} = {\bf b}$ can be solved by an s-term conjugate gradient method. We show that, except for a few anomalies, the class $CG(s)$ consists of matrices A for which conjugate gradient methods are already known. These matrices are the Hermitian matrices, $A^ * = A$, and the matrices of the form $Ae^{i\theta} (dI + B)$, with $B^ * = - B$.