The conjugate gradient (CG) algorithm is well-known to have excellent theoretical properties for solving linear systems of equations $Ax = b$ where the $n\times n$ matrix $A$ is symmetric positive definite. However, for extremely ill-conditioned matrices the CG algorithm performs poorly in practice. In this paper, we discuss an adaptive preconditioning procedure which improves the performance of the CG algorithm on extremely ill-conditioned systems. We introduce the preconditioning procedure by applying it first to the steepest descent algorithm. Then, the same techniques are extended to the CG algorithm, and convergence to an $\epsilon$-solution in $\O(\log\det(A) + \sqrt{n}\log\epsilon^{-1})$ iterations is proven, where $\det(A)$ is the determinant of the matrix.
Citation
Technical Report, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205, October 2004.