Version 1.4.0

21st June 2016

Recent Changes

• Integer
• Long Integer

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 undeﬁned behaviour.

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

To reduce the amount of matrix data read during the analysis, supervariables of $A$ may be identiﬁed. A supervariable is a set of columns of $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 aﬀect the number of entries in $L$ to be identiﬁed and allows fast algorithms to be used in determining the exact structure of $L$.

A supernode is a set of columns that have the same pattern in the matrix $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 eﬃciency in a subsequent factorization phase, supernodes may be merged through a supernode amalgamation heuristic.

HSL_MC78 supports the use of $2×2$ and larger block pivots.