3rd August 2021

User documentation

- Integer
- Long Integer

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.