PMORSy: parallel sparse matrix ordering software for fill-in minimization^†

† This work was presented at the 5th International Conference on Network Analysis, held in Nizhni Novgorod, Russia, 18–20 May 2015.

Abstract

In this paper we present PMORSy—a new parallel software package for symmetric sparse matrix ordering on shared memory systems. The NP-complete fill-in minimization problem is solved by means of multilevel nested dissection algorithm with modifications for vertex separators. Parallel processing is done in a task-based fashion with the granularity tuning. We employ threading techniques on shared memory using OpenMP 3.0 technology as opposed to the Message Passing Interface-based approach widely used for parallel sparse matrix ordering. Experimental results on symmetric matrices from the University of Florida Sparse Matrix Collection and matrices from finite-element analysis of three-dimensional strength problems show that our implementation is competitive to the ParMETIS and PT-Scotch libraries both in ordering quality and performance. The PMORSy library is publicly available from the Lobachevsky State University Supercomputing Center web-site.

Keywords:

• fill-in minimization
• multilevel nested dissection
• sparse matrix ordering
• Cholesky factorization
• parallel computing
• task-based parallel processing

Acknowledgements

The authors would like to thank Dmitry Akhmedzhanov, Sergey Bastrakov, Alexey Liniov, Alexander Sysoyev and Nikolai Zolotykh for useful comments and discussions.

Disclosure statement

No potential conflict of interest was reported by the authors.

Notes

† This work was presented at the 5th International Conference on Network Analysis, held in Nizhni Novgorod, Russia, 18–20 May 2015.

Additional information

Funding

The study was partially supported by the RFBR, research project No. 14-01-3145514 and by The Ministry of Education and Science of the Russian Federation, research assignment No. 1.115.2014/K.