In the fan-out and fan-in factorization algorithms, the necessary
information flow between columns is mediated by factor columns or
aggregate update columns, respectively. Another alternative is a *
multi-frontal* method, in which update information is mediated through a
series of front matrices. In a sense, this represents an intermediate
strategy, since the effect of each factor column is incorporated
immediately into a front matrix, but its eventual incorporation into
the ultimate target column is delayed until actually needed. The
principal computational advantage of multi-frontal methods is that the
frontal matrices are treated as dense matrices, and hence updating
operations on them are much more efficient than the corresponding
operations on sparse data structures that require indirect addressing.
Unfortunately, although the updating computations employ simple dense
arrays, the overall management of the front matrices is relatively
complicated. As a consequence, multi-frontal methods are difficult to
specify succinctly, so we will not attempt to do so here, but note that
multi-frontal methods have been implemented for both shared-memory
(e.g., [74,75]) and
distributed-memory
(e.g., [76,77])
parallel
computers, and are among the most effective methods known for sparse
factorization in all types of computational environments. For a unified
description and comparison of parallel fan-in, fan-out and multi-frontal
methods, see [78].

In this brief section on parallel direct methods for sparse systems, we
have concentrated on numeric Cholesky factorization for SPD matrices.
We have omitted many other aspects of the computation, even for the SPD
case: computing the ordering in parallel, symbolic factorization, and
triangular solution. More generally, we have omitted any discussion of
* LU* factorization for general sparse square matrices or * QR*
factorization
for sparse rectangular matrices. Instead we have concentrated on
identifying the major features that distinguish parallel sparse
factorization from the dense case and examining the performance
implications of those differences.