Direct solution of sparse linear system of equations consists of three phases — Analysis, Numerical Factorization and Numerical Solution. The analysis phase has an ordering step that aims at reducing the fill-ins created during numerical factorization. This in turn reduces the space and time required by the solver program. Ordering, being NP-complete, is handled using heuristics. This work investigates the Minimum Fill-in (MF) algorithm, and presents a number of improvements in order to enhance its performance. The enhancements discussed are based on multiple elimination strategies derived from the ideas of independent sets and supernodes. A parallelization approach using nested dissection is also presented, along with a comparison of the modified heuristic and the Approximate Mean Minimum local Fill-in (AMMF) heuristic. The implementation results show that Sequential AMMF appears to be the best choice for small matrices. For large matrices (that cannot be processed on a single processing node), parallelized version of Multiple MF is more efficient.
展开▼
