Conjugate Gradient Methods for Indefinite Systems
Abstract¶
Conjugate gradient methods have often been used to solve a wide variety of numerical problems, including linear and nonlinear algebraic equations, eigenvalue problems and minimization problems. These applications have been similar in that they involve large numbers of variables or dimensions. In these circumstances any method of solution which involves storing a full matrix of this large order, becomes inapplicable. Thus recourse to the conjugate gradient method may be the only alternative. For problems in linear equations, the conjugate gradient method requires that the coefficient matrix A, is not only symmetric but also positive definite. This restriction is also implicit in applications to unconstrained minimization. Yet there are many problems in which non-trivial equations have to be added to what would otherwise be an elliptic system. One example is the restriction to divergence-free vectors in fluid dynamics (linear or nonlinear), and there are various other examples from partial differential equations. Also minimization problems in general, when involving linear or nonlinear equality constraints, provide further examples. In all these cases the coefficient matrix of the linear model has the form A = [G -C; -C^T 0]. It is usually possible to augment the quadratic objective function (see (2.5) below) with a penalty term, so that the submatrix G is positive definite. However the matrix A is clearly indefinite (that is neither positive nor negative semi-definite) except in trivial cases. It is usually possible to apply the conjugate gradient algorithm to indefinite systems, the difficulty being the possibility of division by zero, and hence breakdown of the algorithm. There is also the possibility of substantial error growth when this situation is almost achieved. This paper will review some suggestions which have been made for modifying the conjugate gradient method, or proposing similar types of method, to deal with symmetric indefinite problems. Attention is restricted to deriving methods which do not break down, and which can be implemented using only a few vectors of storage. One possible approach is the hyperbolic pairs method of Luenberger [5], which is shown to be unsatisfactory as it stands. A new formulation is proposed which reduces to the hyperbolic pairs method in the limiting case; nonetheless the best way of applying the method is not entirely clear, and there are reasons to think that the stability problem is not completely solved. Another type of method is that in which the sum of squares of residuals is minimized. Two ways which have been proposed for doing this are described, and it is shown that one is to be preferred. It provides a viable algorithm for application to indefinite problems. However the algorithm is not entirely convenient for application to certain types of problem. The algorithm is also shown to be directly related to others which have been proposed, in particular the method of biconjugate gradients. This latter method is described in some detail. It is also shown that another different algorithm can be derived from the biconjugate gradient algorithm, and which is suitable for indefinite systems. Relationships are stated which exist between these methods derived from biconjugate gradients, and the standard conjugate gradient method. In addition some recent work by Paige and Saunders [6] is reviewed, in which a new method is generated, based on the explicit use of the orthogonal reduction of a tridiagonal matrix to upper triangular form. The formulae which are entailed in using this method are quite complicated. However it is shown that Paige and Saunders' method is equivalent to the second method based on the biconjugate gradient algorithm, although the latter provides the more convenient recurrence relations. Finally a few other possibilities which have been suggested, and which are potentially suitable for the indefinite problem are discussed. None of them are currently felt to be as promising as the two methods derived from biconjugate gradients, for this type of application.
Summary¶
Fletcher reviews and develops conjugate-gradient-like methods for symmetric indefinite linear systems, where ordinary conjugate gradients can break down. The paper is an important early source for biconjugate-gradient-style recurrences and for storage-efficient Krylov methods suited to constrained and saddle-point linear systems.