Geodesic
Experimental evaluation of algorithms in the parallel multilevel nested dissection method
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 6 (2017) no. 1, pp. 38-55 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Direct methods for solving large sparse systems of linear equations make use of reordering of rows and columns of the original matrix. The goal of this procedure is to reduce the fill-in during the subsequent numerical factorization. Finding the ordering with the minimum fill-in is NP-complete. Heuristic methods are used to solve this problem. These methods can be evaluated for both quality (fill-in) and time to obtain an ordering. The multilevel nested dissection method performs reasonably well in terms of both criteria and is one of the most widely used reordering methods. The method has some parallelization potential, which is utilized in several implementations (ParMETIS, mtMETIS, PT-SCOTCH, PMORSy). However, low arithmetic intensity, irregular memory access pattern, workload imbalance and the trade-off between run time and quality motivates further investigation of the method. This paper presents the comparison of the algorithms used on several stages of the multilevel nested dissection method in terms of fill-in and run time on a parallel system. The implementation and experiments are done using the parallel PMORSy library, which outperforms competitors on some matrices from the University of Florida sparse matrix collection. As the result we distinguish the most promising combination of the algorithms and improve the quality and performance of PMORSy.
Keywords: multilevel nested dissection, sparse matrix ordering, parallel algorithm. 
@article{VYURV_2017_6_1_a2,
     author = {A. Yu. Pirova and N. Yu. Kudriavtsev and I. B. Meyerov},
     title = {Experimental evaluation of algorithms in the parallel multilevel nested dissection method},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a Vy\v{c}islitelʹna\^a matematika i informatika},
     pages = {38--55},
     year = {2017},
     volume = {6},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURV_2017_6_1_a2/}
}
TY  - JOUR
AU  - A. Yu. Pirova
AU  - N. Yu. Kudriavtsev
AU  - I. B. Meyerov
TI  - Experimental evaluation of algorithms in the parallel multilevel nested dissection method
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
PY  - 2017
SP  - 38
EP  - 55
VL  - 6
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VYURV_2017_6_1_a2/
LA  - ru
ID  - VYURV_2017_6_1_a2
ER  - 
%0 Journal Article
%A A. Yu. Pirova
%A N. Yu. Kudriavtsev
%A I. B. Meyerov
%T Experimental evaluation of algorithms in the parallel multilevel nested dissection method
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika
%D 2017
%P 38-55
%V 6
%N 1
%U http://geodesic.mathdoc.fr/item/VYURV_2017_6_1_a2/
%G ru
%F VYURV_2017_6_1_a2
A. Yu. Pirova; N. Yu. Kudriavtsev; I. B. Meyerov. Experimental evaluation of algorithms in the parallel multilevel nested dissection method. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ Vyčislitelʹnaâ matematika i informatika, Tome 6 (2017) no. 1, pp. 38-55. http://geodesic.mathdoc.fr/item/VYURV_2017_6_1_a2/

[1] T. Bui, C. Jones, “A Heuristic for Reducing Fill in Sparse Matrix Factorization”, 6th SIAM Conference Parallel Processing for Scientific Computing, 1993, 445–452

[2] C. Chevalier, F. Pellegrini, “PT-Scotch: A Tool for Efficient Parallel Graph Ordering”, Parallel Computing, 34:6 (2008), 318–331 | DOI

[3] T. A. Davis , Y. Hu, “The University of Florida Sparse Matrix Collection”, ACM Transactions on Mathematical Software (TOMS), 38:1 (2011), 1 | DOI

[4] A. George et al., “Sparse Cholesky Factorization on a Local-memory Multiprocessor”, SIAM J. on Scientific and Statistical Computing, 9:2 (1988), 327–340 | DOI

[5] A. George, “Nested Dissection of a Regular Finite Element Mesh”, SIAM J. on Numerical Analysis, 10:2 (1973), 345–363 | DOI

[6] A. George, J. W. H. Liu, “An Automatic Nested Dissection Algorithm for Irregular Finite Element Problems”, SIAM J. on Numerical Analysis, 15:5 (1978), 1053–1069 | DOI

[7] G. Karypis, V. Kumar, ParMetis: Parallel Graph Partitioning and Sparse Matrix Ordering Library, Tech. Rep. TR 97-060, University Of Minnesota, Department Of Computer Science, 1997

[8] G. Karypis, V. Kumar, “A Fast and High Quality Multilevel Scheme for Partitioning Irregular Graphs”, SIAM J. on Scientific Computing, 20:1 (1998), 359–392 | DOI

[9] G. Karypis, V. Kumar, “Analysis of Multilevel Graph Partitioning”, Proceedings of the 1995 ACM/IEEE conference on Supercomputing, ACM, 1995, 29

[10] G. Karypis, V. Kumar, METIS. A Software Package for Partitioning Unstructured Graphs, Partitioning Meshes, and Computing Fill-reducing Orderings of Sparse Matrices, Technical Report, University of Minnesota, Department of Computer Science and Engineering, 1998

[11] D. LaSalle, G. Karypis, “Efficient Nested Dissection for Multicore Architectures”, EuroPar 2015: Parallel Processing, Springer, Berlin Heidelberg, 2015, 29

[12] F. Pellegrini, Scotch and libScotch 6.0 User’s Guide, Technical Report LaBRI, 2012

[13] F. Pellegrini, MUMPS User Group Meeting, 2013, arXiv: nucl-ex/0607012

[14] A. Pirova, I. Meyerov, “MORSy — a New Tool for Sparse Matrix Reordering”, An International Conference on Engineering and Applied Sciences Optimization (Kos Island, Greece, 4-6 June 2014), eds. M. Papadrakakis, M.G. Karlaftis, N.D. Lagaros, 1952–1964

[15] A. George, J. W. H. Liu, “PMORSy: Parallel Sparse Matrix Ordering Software for Fill-in Minimization”, Optimization Methods and Software, 32:2 (2017), 274–289 | DOI

[16] A. Pothen, “Graph Partitioning Algorithms with Applications to Scientific Computing”, Parallel Numerical Algorithms, Springer Netherlands, 1997, 323–268 | DOI

[17] W. Tinney, J. Walker, “Direct Solutions of Sparse Network Equations by Optimally Ordered Triangular Factorization”, Proceedings of the IEEE, 55:11 (1967), 1801–1809 | DOI

[18] M. Yannakakis, “Computing the Minimum Fill-in is NP-complete”, SIAM J. on Algebraic and Discrete Methods, 2:1 (1981), 77–79 | DOI

[19] 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, 16:3 (2015), 407–420

[20] N. V. Starostin, “The Multilevel Iteration Algorithm for Graph Decomposition”, Operation Systems and Information Technologies, 61:3 (2015), 27–30