3rd January 2012

# 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).