A column pre-ordering strategy for the unsymmetric-pattern multifrontal method Academic Article

abstract

• A new method for sparse LU factorization is presented that combines a column pre-ordering strategy with a right-looking unsymmetric-pattern multifrontal numerical factorization. The column ordering is selected to give a good a priori upper bound on fill-in and then refined during numerical factorization (while preserving the bound). Pivot rows are selected to maintain numerical stability and to preserve sparsity. The method analyzes the matrix and automatically selects one of three pre-ordering and pivoting strategies. The number of nonzeros in the LU factors computed by the method is typically less than or equal to those found by a wide range of unsymmetric sparse LU factorization methods, including left-looking methods and prior multifrontal methods.

authors

• Davis, Timothy

published proceedings

• ACM TRANSACTIONS ON MATHEMATICAL SOFTWARE

author list (cited authors)

• Davis, T. A.

citation count

• 280

complete list of authors

• Davis, TA

publisher

• Association for Computing Machinery (ACM)  Publisher

published in

• ACM Transactions on Mathematical Software  Journal

keywords

• Algorithms
• Experimentation
• Linear Equations
• Multifrontal Method
• Ordering Methods
• Performance
• Sparse Nonsymmetric Matrices

Digital Object Identifier (DOI)

• 10.1145/992200.992205

start page

• 165

end page

• 195

volume

• 30

issue

• 2

URL

• http://dx.doi.org/10.1145/992200.992205