Overview

Unfortunately, there is no stable scheme exactly analogous to Gaussian elimination with partial pivoting; one cannot construct an algorithm for which there is a bound on the element growth of the sequence A ^{( k)} when at each stage only one column of A ^{( k)} is examined.

- JAMES R. BUNCH and LINDA KAUFMAN, Some Stable Methods for Calculating Inertia and Solving Symmetric Linear Systems (1977)

The comparison count is much less ... than for the complete pivoting scheme, and in practice this fact has had a much larger impact than originally anticipated, sometimes cutting the execution time by about 40%.

- JAMES R. BUNCH and LINDA KAUFMAN, Some Stable Methods for Calculating Inertia and Solving Symmetric Linear Systems (1977)

This fixed inertia property is why skew-symmetric matrices are easier to decompose than symmetric indefinite matrices.

- JAMES R. BUNCH, A Note on the Stable Decomposition of Skew-Symmetric Matrices (1982)

Overview

A symmetric matrix is indefinite if ( X ^T Ax)( y ^T Ay) < 0 for some , or, equivalently, if A has both positive and negative eigenvalues. Linear systems with symmetric indefinite coefficient matrices arise in many applications, including least squares problems, optimization, and discretized incompressible Navier-Stokes equations. How can we solve Ax = b efficiently?

Gaussian elimination with partial pivoting (GEPP) can be used to compute the factorization PA = LU, but it does not take advantage of the symmetry...