Stable Factorizations of Symmetric Tridiagonal and Triadic Matrices

Abstract

We call a matrix triadic if it has no more than two nonzero off-diagonal elements in any column. A symmetric tridiagonal matrix is a special case. In this paper we consider $LXL^T$ factorizations of symmetric triadic matrices, where $L$ is unit lower triangular and $X$ is diagonal, block diagonal with $1\!\times\!1$ and $2\!\times\!2$ blocks, or the identity with $L$ lower triangular. We prove that with diagonal pivoting, the $LXL^T$ factorization of a symmetric triadic matrix is sparse, study some pivoting algorithms, discuss their growth factor and performance, analyze their stability, and develop perturbation bounds. These factorizations are useful in computing inertia, in solving linear systems of equations, and in determining modified Newton search directions.