A hybrid iterative method for symmetric positive definite linear systems

A hybrid iterative scheme that combines the Conjugate Gradient (CG) method with Richardson iteration is presented. This scheme is designed for the solution of linear systems of equations with a large sparse symmetric positive definite matrix. The purpose of the CG iterations is to improve an available approximate solution, as well as to determine an interval that contains all, or at least most, of the eigenvalues of the matrix. This interval is used to compute iteration parameters for Richardson iteration. The attraction of the hybrid scheme is that most of the iterations are carried out by the Richardson method, the simplicity of which makes efficient implementation on modern computers possible. Moreover, the hybrid scheme yields, at no additional computational cost, accurate estimates of the extreme eigenvalues of the matrix. Knowledge of these eigenvalues is essential in some applications.Research supported in part by NSF grant DMS-9409422.Research supported in part by NSF grant DMS-9205531.