Stable Factorizations of Symmetric Tridiagonal and Triadic Matrices

 Title Stable Factorizations of Symmetric Tridiagonal and Triadic Matrices Publication Type Journal Articles Year of Publication 2006 Authors Fang H-ren, O'Leary DP Journal SIAM J. on Matrix Analysis and Applications Volume 28 Pagination 576 - 595 Date Published 2006/// 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.