Combined Unifrontal/Multifrontal Method for Unsymmetric Sparse Matrices

摘要

The authors discuss the organization of frontal matrices in multifrontal methodsfor the solution of large sparse sets of unsymmetric linear equations. In the multifrontal method, work on a frontral matrix can be suspended, the frontal matrix can be stored for later reuse, and a new frontal matrix can be generated. There are thus several frontal matrices stored during the factorization and one or more or these are assembled (summed) when creating a new frontal matrix. Although this means that arbitrary sparsity patterns can be handled efficiently, extra work is required to sum the frontal matrices together and can be costly because indirect addressing is required. The (uni-)frontal method avoids this extra work by factorizing the matrix with a single frontal matrix. Rows and columns are added to the frontal matrix, and pivot rows and columns are removed. Data movement is simpler, but higher fill-in can result if the matrix cannot be permuted into a variable-band form with small profile. The authors consider a combined unifrontal/multifrontal algorithm to enable general fill-in reduction orderings to be applied without the data movement of previous multifrontal approaches. the authors discuss this technique in the context of a code designed for the solution of sparse systems with unsymmetric pattern.