PMORSy: parallel sparse matrix ordering software for fill-in minimization†. (4th March 2017)

• Record Type: Journal Article
• Authors: Pirova, Anna; Meyerov, Iosif; Kozinov, Evgeniy; Lebedev, Sergey
• Is Part Of: Optimization methods and software. Volume 32:Number 2(2017)
• Page Start: 274
• Page End: 289
• Publication Date: 2017-03-04
• Subjects: fill-in minimization -- multilevel nested dissection -- sparse matrix ordering -- Cholesky factorization -- parallel computing -- task-based parallel processing; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2016.1193177
• Languages: English
• ISSNs: 1055-6788

Abstract

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.