HSL_MA74: Unsymmetric full matrix: partial or complete factorization and solution

Given a dense unsymmetric \(n \times n\) matrix \(\mathbf{A}\), HSL_MA74 performs partial factorizations and solutions of corresponding sets of equations. It is designed as a kernel for use in a frontal or multifrontal solver or may be used to factorize and solve a full system of equations.

Eliminations are limited to the leading \(p \le n\) rows and columns. Stability considerations may lead to \(q \le p\) eliminations being performed. The factorization takes the form \[\mathbf{PAQ} = \left ( \begin{array}{cc} \mathbf{L}_1 \\ \mathbf{L}_2 & \mathbf{I} \end{array} \right ) \left ( \begin{array}{cc} \mathbf{D}_1 \\ & \mathbf{A}_2 \end{array} \right ) \left ( \begin{array}{cc} \mathbf{U}_1 & \mathbf{U}_2 \\ & \mathbf{I} \end{array} \right ) ,\] where \(\mathbf{P}\) and \(\mathbf{Q}\) are permutation matrices, \(\mathbf{L} _1\) and \(\mathbf{U} _1\) are unit lower and unit upper triangular matrices of order \(q\), and \(\mathbf{D} _1\) is the diagonal of order \(q\). The permutation matrices \(\mathbf{P}\) and \(\mathbf{Q}\) are of the form

\[\mathbf{P} = \left ( \begin{array}{cc} \mathbf{P}_1 \\ & \mathbf{I} \end{array} \right ) \;\; \mathrm{and} \;\; \mathbf{Q} = \left ( \begin{array}{cc} \mathbf{Q}_1 \\ & \mathbf{I} \end{array} \right ) ,\] where \(\mathbf{P} _1\) and \(\mathbf{Q} _1\) are of order \(p\).

Subroutines are provided for partial solutions, that is, solving systems of the form

\[\left ( \begin{array}{cc} \mathbf{L} _{1} \\ \mathbf{L} _{2} & \mathbf{I} \end{array} \right ) \mathbf{X} = \mathbf{B},\; \left ( \begin{array}{cc} \mathbf{D}_1 \\ & \mathbf{I} \end{array} \right ) \mathbf{X} = \mathbf{B},\; \left ( \begin{array}{cc} \mathbf{D}_1 \\ & \mathbf{I} \end{array} \right ) \left ( \begin{array}{cc} \mathbf{U} _{1} & \mathbf{U} _{2} \\ & \mathbf{I} \end{array} \right ) \mathbf{X} = \mathbf{B},\] and \[\left ( \begin{array}{cc} \mathbf{U} _{1} & \mathbf{U} _{2} \\ & \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}\).

Subroutines are also provided for partial solutions to transpose systems, that is, solving systems of the form \[\left ( \begin{array}{cc} \mathbf{U} _{1}^T \\ \mathbf{U} _{2}^T & \mathbf{I} \end{array} \right ) \mathbf{X} = \mathbf{B},\; \left ( \begin{array}{cc} \mathbf{D}_1 \\ & \mathbf{I} \end{array} \right ) \left ( \begin{array}{cc} \mathbf{L} _{1}^T & \mathbf{L} _{2}^T \\ & \mathbf{I} \end{array} \right ) \mathbf{X} = \mathbf{B}, \; \left ( \begin{array}{cc} \mathbf{L} _{1}^T & \mathbf{L} _{2}^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}\).

Options are included for threshold partial pivoting, threshold diagonal pivoting, threshold rook pivoting, and static pivoting.

Note: If a full factorization and solution of one or more sets of equations is required \((p = n)\), routines from the LAPACK library may be used (and may be more efficient).