Stable Factorizations of Symmetric Tridiagonal and Triadic Matrices

TitleStable Factorizations of Symmetric Tridiagonal and Triadic Matrices
Publication TypeJournal Articles
Year of Publication2006
AuthorsFang H-ren, O'Leary DP
JournalSIAM J. on Matrix Analysis and Applications
Pagination576 - 595
Date Published2006///

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.