A parallel multilevel nested dissection algorithm for shared-memory computing systems
Numerical methods and programming, Tome 16 (2015) no. 3, pp. 407-420
Voir la notice de l'article provenant de la source Math-Net.Ru
This paper deals with the NP-complete problem of finding a symmetric positive definite sparse matrix ordering that minimizes the Cholesky factor fill-in. For this purpose, heuristic approaches based on graph algorithms are applied. A new parallel ordering algorithm for shared-memory computing systems is proposed. The modified multilevel nested dissection algorithm from the recently presented MORSy library is used as a basis for ordering. The parallel processing is done in a task-based fashion. It uses the OpenMP 3.0 task parallelism relying on the dynamic load balancing implemented during the OpenMP runtime. The numerical experiments were performed using a number of symmetric positive definite matrices from the University of Florida Sparse Matrix Collection. The experimental results show the competitiveness of the proposed implementation on shared memory systems compared to the widely used ParMETIS library. In our experiments, the parallel MORSy version provides a better ordering than ParMETIS on all but one matrix in terms of the Cholesky factor fill-in and outperforms ParMETIS in most cases. The parallel MORSy version is publicly available from the Supercomputing Center of Lobachevsky State University of Nizhni Novgorod.
Keywords:
multilevel nested dissection, sparse matrix ordering, Cholesky factorization, parallel algorithms, shared-memory computing systems, high-performance computing.
@article{VMP_2015_16_3_a7,
author = {A. Yu. Pirova and I. B. Meyerov and E. A. Kozinov and S. A. Lebedev},
title = {A parallel multilevel nested dissection algorithm for shared-memory computing systems},
journal = {Numerical methods and programming},
pages = {407--420},
publisher = {mathdoc},
volume = {16},
number = {3},
year = {2015},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/VMP_2015_16_3_a7/}
}
TY - JOUR AU - A. Yu. Pirova AU - I. B. Meyerov AU - E. A. Kozinov AU - S. A. Lebedev TI - A parallel multilevel nested dissection algorithm for shared-memory computing systems JO - Numerical methods and programming PY - 2015 SP - 407 EP - 420 VL - 16 IS - 3 PB - mathdoc UR - http://geodesic.mathdoc.fr/item/VMP_2015_16_3_a7/ LA - ru ID - VMP_2015_16_3_a7 ER -
%0 Journal Article %A A. Yu. Pirova %A I. B. Meyerov %A E. A. Kozinov %A S. A. Lebedev %T A parallel multilevel nested dissection algorithm for shared-memory computing systems %J Numerical methods and programming %D 2015 %P 407-420 %V 16 %N 3 %I mathdoc %U http://geodesic.mathdoc.fr/item/VMP_2015_16_3_a7/ %G ru %F VMP_2015_16_3_a7
A. Yu. Pirova; I. B. Meyerov; E. A. Kozinov; S. A. Lebedev. A parallel multilevel nested dissection algorithm for shared-memory computing systems. Numerical methods and programming, Tome 16 (2015) no. 3, pp. 407-420. http://geodesic.mathdoc.fr/item/VMP_2015_16_3_a7/