On Direct Methods for Solving Symmetric Systems of Linear Equations

摘要

There has been no stable direct method for solving symmetric systems of linear equations which takes advantage of the symmetry. If the system is also positive definite, then fast, stable direct methods (e.g., Cholesky and symmetric Gaussian elimination) exist which preserve the symmetry. These methods are unstable for symmetric indefinite systems. Such systems often occur in the calculation of eigenvectors. Gaussian elimination with partial or complete pivoting is currently recommended for solving symmetric indefinite systems, and here symmetry is lost. A generalization of symmetric Gaussian elimination is presented here, called the diagonal pivoting method, in which pivots of order two as well as one are allowed in the decomposition. It is shown that the diagonal pivoting method for symmetric indefinite matrices takes advantage of symmetry so that only 1/6 n cubed multiplications, at most 1/3 n cubed additions, and 1/2 n squared storage locations are required to solve A x = b, where A is a non-singular symmetric matrix of order n. Furthermore, it is shown that the method is nearly as stable as Gaussian elimination with complete pivoting, while requiring only half the number of operations and half the storage. (Author)