An Optimal Agorithm for Symbolic Factorization of Symmetric Matrices
Alan D. George, Joseph W. H. Liu · SIAM Journal on Computing · 1980
A fundamental problem in the computer solution of a sparse, N by N, positive definite system of equations $Ax = b$ is, given the structure of A, to determine the structure of its Cholesky factor L, where $A = LL^T $. This problem arises because it is often desirable to set up a data structure for L before the numerical computation is performed, and in order to do this we must know the positions of the nonzeros of L. We describe a representation$\mathcal {R}_L $ for L which typically requires far fewer data items than the number of nonzeros in L, and an algorithm is then described which generates $\mathcal {R}_L $. The time and space complexity of the algorithm is shown to be $O(|A|,|\mathcal {R}_L |)$, and can never be worse than $O(|L|)$. Here $|\mathcal {R|}_L |$ denotes the number of items in the data structure for L, and $|A|$ (and $|L|$ denote the number of nonzeros in A and L respectively. For a certain class of problems, we show that the execution time of the algorithm is $O(N)$, even though $|L|$ is $O(N\log N)$. We also provide some numerical results showing that the algorithm can be implemented so that the program performance reflects its theoretically predicted behavior.