Conjugate Gradient Method

The conjugate gradient method is an algorithm for finding the nearest local minimum of a function of  variables which presupposes that the gradient of the function can be computed. It uses conjugate directions instead of the local gradient for going downhill. If the vicinity of the minimum has the shape of a long, narrow valley, the minimum is reached in far fewer steps than would be the case using the method of steepest descent.

For a discussion of the conjugate gradient method on vector and shared memory computers, see Dongarra et al. (1991). For discussions of the method for more general parallel architectures, see Demmel et al. (1993) and Ortega (1988) and the references therein.

REFERENCES:

Axelsson, O. and Barker, A. Finite Element Solution of Boundary Value Problems: Theory and Computation. Orlando, Florida: Academic Press, 1984.

Barrett, R.; Berry, M.; Chan, T. F.; Demmel, J.; Donato, J.; Dongarra, J.; Eijkhout, V.; Pozo, R.; Romine, C.; and van der Vorst, H. Templates for the Solution of Linear Systems: Building Blocks for Iterative Methods, 2nd ed. Philadelphia, PA: SIAM, 1994. http://www.netlib.org/linalg/html_templates/Templates.html.

Brodile, K. W. "Unconstrained Minimization." §3.1.7 in The State of the Art in Numerical Analysis (Ed. D. A. E. Jacobs). London: Academic Press, pp. 229-268, 1977.

Bulirsch, R. and Stoer, J. "The Conjugate-Gradient Method of Hestenes and Stiefel." §8.7 in Introduction to Numerical Analysis. New York: Springer-Verlag, 1991.

Concus, P.; Golub, G.; and O'Leary, D. "Generalized Conjugate Gradient Method for the Numerical Solution of Elliptic Partial Differential Equations." In Sparse Matrix Computations (Ed. J. Bunch and D. Rose). New York: Academic Press, pp. 309-332, 1976.

Demmel, J.; Heath, M.; and van der Vorst, H. "Parallel Numerical Linear Algebra." In Acta Numerica, Vol. 2. Cambridge, England: Cambridge University Press, 1993.

Dongarra, J.; Duff, I.; Sorensen, D.; and van der Vorst, H. Solving Linear Systems on Vector and Shared Memory Computers. Philadelphia, PA: SIAM, 1991.

Golub, G. and O'Leary, D. "Some History of the Conjugate Gradient and Lanczos Methods." SIAM Rev. 31, 50-102, 1989.

Golub, G. H. and Van Loan, C. F. Matrix Computations, 3rd ed. Baltimore, MD: Johns Hopkins University Press, p. 310, 1996.

Hackbusch, W. Iterative Lösung großer schwachbesetzter Gleichungssysteme. Stuttgart, Germany: Teubner, 1991.

Kaniel, S. "Estimates for Some Computational Techniques in Linear Algebra." Math. Comput. 20, 369-378, 1966.

Ortega, J. M. Introduction to Parallel and Vector Solution of Linear Systems. New York: Plenum Press, 1988.

Polak, E. "Conjugate Gradient in Rn" in Computational Methods in Optimization." §2.3 in Computational Methods in Optimization. New York: Academic Press, pp. 44-66, 1971.

Press, W. H.; Flannery, B. P.; Teukolsky, S. A.; and Vetterling, W. T. Numerical Recipes in FORTRAN: The Art of Scientific Computing, 2nd ed. Cambridge, England: Cambridge University Press, pp. 413-417, 1992.

Reid, J. "On the Method of Conjugate Gradients for the Solution of Large Sparse Systems of Linear Equations." In Large Sparse Sets of Linear Equations: Proceedings of the Oxford conference of the Institute of Mathematics and Its Applications held in April, 1970 (Ed. J. Reid). London: Academic Press, pp. 231-254, 1971.

van der Sluis, A. and van der Vorst, H. "The Rate of Convergence of Conjugate Gradients." Numer. Math. 48, 543-560, 1986.