PMORSy: parallel sparse matrix ordering software for fill-in minimization
| Autor: | Sergey Lebedev, Iosif B. Meyerov, Anna Pirova, Evgeniy Kozinov |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Control and Optimization
Nested dissection Computer science Applied Mathematics Message Passing Interface 010103 numerical & computational mathematics 02 engineering and technology Sparse approximation Parallel computing 01 natural sciences 020202 computer hardware & architecture Shared memory Cuthill–McKee algorithm 0202 electrical engineering electronic engineering information engineering Symmetric matrix 0101 mathematics Software Sparse matrix Cholesky decomposition |
| Zdroj: | Optimization Methods and Software. 32:274-289 |
| ISSN: | 1029-4937 1055-6788 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|