HSL_MC78: Analysis phase in Cholesky algorithm

Given an elimination order, HSL_MC78 performs common tasks required in the analyse phase of a symmetric sparse direct solver. Either the entire analyse may be performed or individual tasks. No checking is performed on the validity of user data, and failure to supply valid data will result in undefined behaviour.

Given the sparsity pattern of a sparse symmetric matrix \(\mathbf{A}\) and permutation \(\mathbf{P}\), HSL_MC78 finds the pattern of the Cholesky factor \(\mathbf{L}\) such that \(\mathbf{PAP}^{-1}=\mathbf{LL}^T\). The pattern of \(A\) may be provided in either assembled or elemental format. The permutation \(\mathbf{P}\) is referred to as the elimination (pivot) order.

To reduce the amount of matrix data read during the analysis, supervariables of \(\mathbf{A}\) may be identified. A supervariable is a set of columns of \(\mathbf{A}\) that have the same sparsity pattern.

An elimination tree is built that describes the structure of the Cholesky factor in terms of data dependence between pivotal columns. This allows permutations of the elimination order that do not affect the number of entries in \(\mathbf{L}\) to be identified and allows fast algorithms to be used in determining the exact structure of \(\mathbf{L}\).

A supernode is a set of columns that have the same pattern in the matrix \(\mathbf{L}\). This pattern is stored as a single row list for each supernode. The condensed version of the elimination tree consisting of supernodes is referred to as the assembly tree. To increase efficiency in a subsequent factorization phase, supernodes may be merged through a supernode amalgamation heuristic.

HSL_MC78 supports the use of \(2\times 2\) and larger block pivots.