A taxonomy of column-based Cholesky factorizations
Cleve Ashcraft · 1996
Column-based Cholesky A = $LL\sp{T}$ factorizations include general sparse, multifrontal, fan-out, fan-in and fan-both. They all deal with columns of A and L and execute the same fundamental computations. They differ in their use of temporary data structures, overhead computation and the types and paths of data communication. We develop a taxonomy that can concisely describe any column-based Cholesky factorization. The primary key is an a template for the accumulation of data. The protoype aggregate tree is the simplest tree, a star-graph, for the general sparse factorization. Multifrontal uses the elimination tree as a template. A taxonomy must not only classify old methods but also predict new methods. After examining the task DAG for multifrontal, we discovered a new partition of the computation that has a radically new aggregate tree, different from the general sparse and tree-based (e.g., multifrontal) families. This leads to an algorithm that, in some sense, optimizes the use of matrix-vector and matrix-matrix computations.