Volume 21, pp. 1-19, 2005.

A tree-based dataflow model for the unsymmetric multifrontal method

Stanley C. Eisenstat and Joseph W. H. Liu

Abstract

This paper introduces a new model to describe the flow of data from update to frontal matrix in the unsymmetric multifrontal method for solving sparse linear systems. The model is based on the elimination tree of an unsymmetric matrix and consists of the edges in this tree together with some cross edges. By symmetrically renumbering the rows and columns of the coefficient matrix using a tree-based postordering, we can permute the matrix into a bordered block triangular form while preserving the elimination tree. The model simplifies when the matrix has this form, which suggests that a multifrontal implementation based on it should be simpler as well. We also extend the model to handle pivoting for stability; compare it with others used in the unsymmetric multifrontal method; and point out the implications for parallelism.

Full Text (PDF) [305 KB]

Key words

sparse matrix factorization, sparse LU decomposition, elimination tree

AMS subject classifications

65F05, 65F50

< Back