## 4 Multifrontal Approach  
### Supernodal Multifrontal (Hsl_ma97)  
In a multifrontal method, the factorization of \(A\) proceeds using a succession of assembly operations into small dense matrices (the so-called _frontal matrices_), interleaved with partial factorizations of these matrices. For each pivot in turn, the multifrontal method first assembles all the rows that contain the pivot. This involves setting up a frontal matrix and adding the rows into it. A row of \(A\) that has been added to the frontal matrix is said to be _assembled_; rows that have not yet been assembled are referred to as _unassembled_. A partial factorization of the frontal matrix is performed (that is, the pivot and any other variables that are only involved in the assembled rows are eliminated). The computed columns of the matrix factor \(L\) are not needed again until the solve phase and so can be stored, while the rest of the frontal matrix (the _generated element_ or _contribution block_), together with a list of the variables involved, is stored separately using a stack. At the next and subsequent stages, not only must unassembled rows of \(A\) that contain the pivot be assembled into the frontal matrix, but so too must any generated elements that contain the pivot. The method generalizes to a supernodal approach by working with blocks of pivots. At each stage, the \(m\times m\) frontal matrix can be expressed in the form  
\[F=\left( \begin{array}{cc}F_{11}&F_{21}^{T}\\ F_{21}&F_{22}\end{array} \right) \tag{4}\]  
where \(F_{11}\) and \(F_{21}\) are _fully summed_, that is, all the entries in the corresponding rows and columns of \(A\) have been assembled, while \(F_{22}\) is not yet fully summed. If \(F_{11}\) has order \(p\) and \(q\) pivots can be chosen stably from \(F_{11}\) (if \(A\) is positive definite, \(p\) pivots can be chosen in order down the diagonal, but in the  
Figure 1: Trapezoidal block column, consisting of a square diagonal block, \(diag\), and a rectangular off-diagonal block, \(rect\). indefinite case, it may only be possible to select \(q<p\) pivots stably), the partial factorization of \(F\) takes the form  
\[F=Q\left( \begin{array}{cc}L_{1}&0\\ L_{2}&I\end{array} \right)\left( \begin{array}{cc}D_{1}&0\\ 0&F_{S}\end{array} \right)\left( \begin{array}{cc}L_{1}^{T}&L_{2}^{T}\\ 0&I\end{array} \right)Q^{T} \tag{5}\]  
where \(Q\) is a permutation matrix of the form  
\[Q=\left( \begin{array}{cc}Q_{1}&0\\ 0&I\end{array} \right)\]  
with \(Q_{1}\) of order \(p\). If \(A\) is positive definite, \(L_{1}\) is lower triangular, and \(D_{1}=I\), the identity matrix; if \(A\) is indefinite, \(L_{1}\) is a unit lower triangular matrix of order \(q\) and \(D_{1}\) is a block diagonal matrix of order \(q\). \(Q_{1}\), \(L_{1}\) and \(D_{1}\) are stored until the solve phase, while the Schur complement \(F_{S}\) is the generated element and is stacked. For the multifrontal solver HSLMA97 we have developed dense linear algebra kernels to perform the partial factorization of the frontal matrices. To simplify the implementation of these, full storage of the (symmetric) frontal matrix is used, enabling blocking to be implemented within a recursive factorization scheme. Given an \(m\times p\) fully summed block \(\left( \begin{array}{c}F_{11}\\ F_{21}\end{array} \right)\) to factorize, if \(p\) is small (\(p\leq 16\)), a _factorization kernel_ is called. Otherwise, the block is divided in half, as shown in Figure 2. The factorization routine is called on the left half, and the right half is updated using the computed factors. The factorization routine is then called on the remaining fully summed columns. In the indefinite case, columns corresponding to delayed pivots are swapped to the end (of the right half) and are included in the factorization routine call with the remaining pivot candidates. As these calls to the factorization routine are recursive, multiple levels of division in both the left and right halves occur in practice.