Unsymmetric-pattern multifrontal methods for parallel sparse LU factorization

Sparse matrix factorization algorithms are typically characterized by irregular memory access patterns that limit their performance on parallel-vector supercomputers. For symmetric problems, methods such as the multifrontal method replace irregular operations with dense matrix kernels. However, no efficient method based primarily on dense matrix kernels exists for matrices whose pattern is very unsymmetric. A new unsymmetric-pattern multifrontal method based on dense matrix kernels is presented. Frontal matrices are rectangular instead of square, and the elimination tree is replaced with a directed acyclic graph. As in the classical multifrontal method, advantage is taken of repetitive structure in the matrix by amalgamating nodes in the directed acyclic graph, potentially giving it high performance on parallel-vector supercomputers. Performance of a sequential version is compared with the classical multifrontal method and a standard unsymmetric solver on an Alliant FX/80 computer. C..