PNNL

Abstract

We propose a method to solve sparse indefinite linear systems that arise at each iteration of an interior method for solving constrained optimization problems. The current gold standard for solving these systems is \LDLT factorization. However, \LDLT requires pivoting during factorization, which substantially increases communication cost. Our novel method solves a large indefinite system by solving multiple smaller positive definite systems, using an iterative solve for the Schur complement and an inner direct solve (via Cholesky factorization) within each iteration. Cholesky is stable without pivoting, thereby reducing communication and allowing reuse of the symbolic factorization. We show that on large systems, our method can efficiently utilize GPUs and outperform \LDLT factorization of the full system.