- A New Conjugate Gradient Algorithm Incorporating Adaptive Ellipsoid Preconditioning Renato D.C. Monteiro (monteiroisye.gatech.edu) Jerome W. O'Neal (jonealisye.gatech.edu) Arkadi Nemirovski (nemirovsie.technion.ac.il) Abstract: 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. Keywords: Conjugate gradient algorithm, steepest descent algorithm, ellipsoid method, condition number, linear systems of equations, convergence rate, polynomial algorithms. Category 1: Convex and Nonsmooth Optimization (Convex Optimization ) Category 2: Nonlinear Optimization (Quadratic Programming ) Category 3: Linear, Cone and Semidefinite Programming (Other ) Citation: Technical Report, School of Industrial and Systems Engineering, Georgia Institute of Technology, Atlanta, GA 30332-0205, October 2004. Download: [Postscript][PDF]Entry Submitted: 10/06/2004Entry Accepted: 10/06/2004Entry Last Modified: 10/06/2004Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.