Search

We discuss the solution of sparse linear equations Ky = z, where K is symmetric and indefinite. Since exact solutions are not always required, direct and iterative methods are both of interest. An important direct method is the Bunch-Parlett factorization K = U sub T DU, where U is triangular and D is block-diagonal. A sparse implementation exists in the form of the Harwell code MA27. An appropriate iterative method is the conjugate-gradient-like algorithm SYMMLQ, which solves indefinite systems with the aid of a positive-definite preconditioner. For any indefinite matrix K, we show that the U sub T DU factorization can be modified at nominal cost to provide an exact preconditioner for SYMMLQ. We give code for overwriting the block-diagonal matrix D produced by MA27. We then study the KKT systems arising in barrier methods for linear and nonlinear programming, and derive preconditioners for use with SYMMLQ. For nonlinear programs we suggest a preconditioner based on the smaller KKT system associated with variables that are not near a bound. For linear programs we propose several preconditioners based on a square nonsingular matrix B that is analogous to the basis matrix in the simplex method. The aim is to facilitate solution of full KKT systems rather than equations of the form AD squared A sub T sub delta pi = r when the latter become excessively ill-conditioned. (kr).

The code performs the parallel decomposition algorithm and is tested on twenty-two small to medium sized "real world" problems. Experiments show that in addition to speedups provided by decomposition alone, performance is improved by using parallel processors."

Final budget recommendations approved by the Stanford University Board of Trustees.