Two-Stage Ordering for Unsymmetric Parallel Row-by-Row Frontal Solvers

摘要

The row-by-row frontal method may be used to solve general large sparse linearsystems of equations. By partitioning the matrix into (nearly) independent blocks and applying the frontal method to each block, a coarse-grained parallel frontal algorithm is obtained. The success of this approach depends on preordering the matrix. This can be done in two stages: (1) order the matrix to bordered block diagonal form (2) order the rows within each block to minimize the size of the frontal matrix. A number of recent papers have considered stage (1). In this paper, an algorithm is proposed for stage (2). For a range of practical examples from chemical process engineering it is shown that the proposed algorithm substantially reduces the block frontal matrix size and, for sufficiently large problems, this can lead to significant reductions in the factorization times when the row-by-row frontal method is implemented in parallel.