Sparsity of Cholesky factors

Question

Hi all!

Let's say I have a positive definite sparse matrix $M$ whose sparsity pattern is known, and let's assume I compute a Cholesky factorization $M = LL^{T}$ of this matrix with all admissible non-zero entries set to, say, one. The factors $L$ are assumed to be sparse.

Will this factorization be valid for every possible positive semi-definite $M$ in the sense that irregardless of the values of the non-zero entries it holds that $M = LL^{T}$, with $L$ always having the sparsity pattern obtained when factorizing the original (positive definite) $M$ but with different values depending on $M$? Some small numerical experiments indicate that this is the case, but can it be proven?

regards
-- Olav

Answer 1

Yes, this is more or less true. See for example Timothy Davis's book, "Direct Methods for Sparse Linear Systems."

You can work out in advance the locations of all possible non-zero entries in $L$ from knowledge of the locations of the nonzeros in $M$. This process is often called "symbolic factorization." Once you've got an actual matrix in hand, the actual "numerical factorization" process is then quite fast. Most library routines for sparse Cholesky factorization exploit this.

Note that it is possible for an entry in $L$ to come out zero due to cancellation of terms in the numerical factorization. In such situations you can end up with zero values stored explicitly in the sparse matrix $L$. Because of this possibility it is not safe to do the symbolic factorization by putting arbitrary numbers into $M$, constructing the Cholesky factor, and recording where the nonzeros are in $L$. Davis's book discusses an algorithm for working out the locations of all possible nonzeros in $L$.

One place where this is particularly helpful is in interior point methods for linear programming. In the primal-dual interior point method, you solve a symmetric and positive definite system of equations of the form $A\theta A^{T} \Delta x =b$, where $\theta$ is a diagonal matrix that changes from iteration to iteration. The locations of the nonzero entries in $A\theta A^{T}$ don't change from iteration to iteration, but the actual values do change. So, you do the symbolic factorization once (during the first iteration) and then do numerical factorization only in each successive iteration of the algorithm.