Compact Clique Tree Data Structures in Spare Matrix Factorizations

Abstract

The design of compact data structures for representing the structure of the Cholesky factor L of a sparse, symmetric positive definite matrix A is considered. The clique tree data structure described in [10] provides a compact representation when the structure of L must be stored explicitly. Two more compact data structures, the compact clique tree and the skeleton clique tree, which represent the structure of L implicitly, i.e., when some computation on the data structure is permitted to obtain the structure of L, are described. The compact clique tree is computed from a clique tree of L, while the skeleton clique tree is computed from the skeleton matrix introduced by Liu [12] and a subset of the information in the clique tree. The relationships between these data structures are considered, and it is proved that the compact clique tree is the smaller of the two. Computational results on some Boeing-Harwell test problems show that these data structures require less pace than either the clique tree or the matrix A. It is also more efficient to generate the structure of L from these data structures than by symbolic factorization on A. The final Section contains a brief discussion of applications, related work, and some questions raised by this work.