**Summary:**
Near the solution, optimization algorithms based on Newton's method generally demonstrate
quadratic convergence. Often, the rate-limiting step in these methods is the calculation of search
directions, which involves solving symmetric linear systems of equations of the form

*Ax = b* at each
iteration. For large-scale problems, these equations can be solved using conjugate-gradient
(CG) methods whenever

*A* is positive definite. However, CG methods can
break down if

*A* is indefinite because the

*LDL'* factorization of the
tridiagonal matrix

*T* in the underlying Lanczos process is unstable.
(Here,

*L* is unit lower triangular and

*D* is diagonal.)

This instability can be overcome by diagonal pivoting strategies that
compute an

*LBL'* factorization of

*T* instead,
where

*B* is

*block* diagonal with 1x1 and 2x2 blocks.
It can be proven that solving a symmetric tridiagonal linear system using a factorization
we proposed with this pivoting strategy is normwise backwards stable,
with the additional feature that it reduces to the

*LDL'* factorization whenever

*T* is positive
definite. This pivoting strategy was used to solve indefinite systems (like the KKT
system arising in optimization or saddle-point systems in numerical PDE).
On these systems, the performance of a
symmetric indefinite factorized CG (ASIFCG) method we developed has a comparable
convergence behavior to those of well-established methods like
SYMMLQ for solving symmetric indefinite systems;
however, it was shown that ASIFCG is more computationally efficient.
More recently, this diagonal pivoting approach was generalized to
solve

*unsymmetric* tridiagonal linear systems, and similar proofs of stability were also obtained.

**Collaborators:**
James Bunch (UC San Diego),
Jennifer Erway (Wake Forest)
**Students:**
Joseph Tyson (Wake Forest)