Multifrontal matrix factorization methods used for solving large, sparse systems of linear equations decompose sparse matrices into overlapping dense submatrices which can be represented by vertices with relationships between submatrices shown via various types of edges. This paper describes the use of graph theory in a new parallel, distributed memory multifrontal method for the LU factorization of sequences of matrices with an identical, unsymmetric pattern. The directed acyclic graphs formed by these vertices and the various edge sets are used to structure the computations, schedule the parallel factorization, and provide a robust capability to dynamically change the pivot ordering to maintain numerical stability. Pivot reordering determines necessary permutations based on a path analysis of two component edge sets. The path properties represented by these edge sets de ne the impacts of these permutations on the structures of the submatrices and the number of nonzeros in the matrix factors. Transitive reductions of these edge sets provide the communications paths needed for parallel implementation.

1. Introduction. Multifrontal techniques for solving large, sparse systems of linear equations are becoming extremely popular because of their unique capabilities to take advantage of high performance computer architectures. Until recently, these methods always assumed a symmetric structure in the system. Recently Davis and Du have developed an unsymmetric pattern multifrontal method based on LU factorization which can signi cantly reduce the amount of required computations for systems with an unsymmetric structure 3]. Comparison studies have shown this method to frequently be the most e cient method for solving such systems 14]. Furthermore, this method has demonstrated signi cant potential for parallelism 10, 11] and can be used e ectively to solve sequences of systems of linear equations that maintain an identical structure such as those that can occur when solving systems of di erential-algebraic equations. These equations arise in many application areas including circuit simulation, chemical engineering, magnetic resonance spectroscopy, and air pollution modeling 4, 12, 15, 17].