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.
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.