HSL_MA64: Indefinite symmetric full matrix: partial or complete factorization and solution

For a full matrix that is real symmetric, complex Hermitian, or complex symmetric, this module performs partial or full factorizations and performs solutions of corresponding sets of equations, paying special attention to the efficient use of cache memory. In the real and complex Hermitian cases, the matrix need not be positive definite. The module performs symmetric interchanges for stability and uses both 1\(\times\)1 and 2\(\times\)2 pivots, assuming that the matrix is well scaled in the sense that changes that are small compared to the largest entry can be tolerated. It is suitable for use in a frontal or multifrontal solver, but may also be used for the direct solution of a full set of equations. Optionally, it may be compiled to use OpenMP.

Eliminations are limited to the leading \(p\) rows and columns. Stability considerations may lead to \(q \le p\) eliminations being performed, but there is an option to force all \(p\) eliminations to be performed. Using an asterisk to represent taking the transpose or Hermitian transpose of a matrix, the factorization takes the form \[\mathbf{P} \mathbf{A} \mathbf{P}^* = \left ( \begin{array}{cc} \mathbf{L}_{11} & \\ \mathbf{L}_{21} & \mathbf{I} \end{array} \right ) \left( \begin{array}{cc} \mathbf{D} & \\ & \mathbf{S}_{22} \end{array} \right ) \left ( \begin{array}{cc} \mathbf{L}_{11}^* & \mathbf{L}_{21}^* \\ & \mathbf{I} \end{array} \right )\] where \(\mathbf{A}\) has order \(n\), \(\mathbf{P}\) is a permutation matrix, \(\mathbf{L}_{11}\) is a unit lower triangular matrix of order \(q\), \(\mathbf{D}\) is block diagonal of order \(q\), and \(\mathbf{S}_{22}\) is a matrix of order \(n-q\). The permutation matrix \(\mathbf{P}\) has the form \[\mathbf{P} = \left ( \begin{array}{cc} \mathbf{P}_1 & \\ & \mathbf{I} \end{array} \right )\] where \(\mathbf{P}_{1}\) is of order \(p\). Each diagonal block of \(\mathbf{D}\) has size one or two.

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 matrix \(\left(\begin{array}{c} \mathbf{L}_{11} \\ \mathbf{L}_{21} \end{array}\right)\) is returned as a sequence of block columns, each of which consists of a triangular matrix packed by columns followed by a rectangular matrix packed by columns.

Subroutines are provided for partial solutions, that is, solving equations of the form \[\left( \begin{array}{cc} \mathbf{L}_{11} & \\ \mathbf{L}_{21} & I \end{array} \right) \mathbf{X} = \mathbf{B}, \quad \left( \begin{array}{cc} \mathbf{D} & \\ & \mathbf{I} \end{array} \right) \mathbf{X} =\mathbf{B},\] \[\left( \begin{array}{cc} \mathbf{D} & \\ &\mathbf{I} \end{array} \right) \left( \begin{array}{cc} \mathbf{L}_{11}^* & \mathbf{L}_{21}^* \\ & \mathbf{I} \end{array}\right) \mathbf{X} =\mathbf{B}, \quad \mathrm{and} \quad \left( \begin{array}{cc} \mathbf{L}_{11}^* & \mathbf{L}_{21}^* \\ & \mathbf{I} \end{array} \right) \mathbf{X} = \mathbf{B}\] and the corresponding equations for a single right-hand side \(b\) and solution \(x\).