Experimental evaluation of algorithms in the parallel multilevel nested dissection method

Direct methods for solving large sparse systems of linear equations make use of reordering of rows and columns of the original matrix. The goal of this procedure is to reduce the fill-in during the subsequent numerical factorization. Finding the ordering with the minimum fill-in is NP-complete. Heuristic methods are used to solve this problem. These methods can be evaluated for both quality (fill-in) and time to obtain an ordering. The multilevel nested dissection method performs reasonably well in terms of both criteria and is one of the most widely used reordering methods. The method has some parallelization potential, which is utilized in several implementations (ParMETIS, mtMETIS, PT-SCOTCH, PMORSy). However, low arithmetic intensity, irregular memory access pattern, workload imbalance and the trade-off between run time and quality motivates further investigation of the method. This paper presents the comparison of the algorithms used on several stages of the multilevel nested dissection method in terms of fill-in and run time on a parallel system. The implementation and experiments are done using the parallel PMORSy library, which outperforms competitors on some matrices from the University of Florida sparse matrix collection. As the result we distinguish the most promising combination of the algorithms and improve the quality and performance of PMORSy.