Geodesic
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/