HSL_MA54: Definite symmetric full matrix: partial or complete factorization and solution

For a matrix that is full, symmetric and positive definite, this module performs partial factorizations and solutions of corresponding sets of equations, paying special attention to the efficient use of cache memory. It uses a modification of the code of Andersen, Gunnels, Gustavson, Reid, and Wasniewski (ACM Trans. on Math. Software, 31, 2005, 201-227). It is designed as a kernel for use in a frontal or multifrontal solver, but may also be used for the direct solution of a full set of equations.

The modification involves limiting the eliminations to the leading \(p\) columns. The factorization takes the form \[\mathbf{A} = \left ( \begin{array}{cc} \mathbf{A} _{11} & \mathbf{A} _{21} ^T \\ \mathbf{A} _{21} & \mathbf{A} _{22} \end{array} \right ) = \left ( \begin{array}{cc} \mathbf{L} _{11} \\ \mathbf{L} _{21} & \mathbf{I} \end{array} \right ) \left ( \begin{array}{cc} \mathbf{I} \\ & \mathbf{S} _{22} \end{array} \right ) \left ( \begin{array}{cc} \mathbf{L} _{11} ^T & \mathbf{L} _{21} ^T \\ & \mathbf{I} \end{array} \right )\] where \(\mathbf{L} _{11}\) is lower triangular and both \(\mathbf{A} _{11}\) and \(\mathbf{L} _{11}\) have order \(p\).

The input format for \(\mathbf{A}\) is that its lower triangular part is held in lower packed format (that is, packed by columns). This format is also used for \(\mathbf{S} _{22}\) on return. The matrices \(\mathbf{L} _{11}\) and \(\mathbf{L} _{21}\) are held as block matrices with blocks of size at most \(nb \times nb\). Internally, we use this blocked format also for \(\mathbf{A} _{22}\).

The module has facilities for rearranging a lower triangular matrix in lower packed format (that is, packed by columns) to this blocked format and vice-versa.

Subroutines are provided for partial forward and back substitution, that is, solving equations of the form \[\left ( \begin{array}{cc} \mathbf{L} _{11} \\ \mathbf{L} _{21} & \mathbf{I} \end{array} \right ) \mathbf{X} = \mathbf{B} \;\; \textrm{and} \; \left ( \begin{array}{cc} \mathbf{L} _{11} ^T & \mathbf{L} _{21} ^T \\ & \mathbf{I} \end{array} \right ) \mathbf{X} = \mathbf{B}\] and the corresponding equations for a single right-hand side \(\mathbf{B}\) and solution \(\mathbf{x}\).

There are also subroutines for solving one or more sets of equations after a full factorization (\(p = n\)) and for extracting the diagonal of \(\mathbf{L} _{11}\).