Geodesic
Parallel partitioning tool for large mesh decomposition
Matematičeskoe modelirovanie, Tome 23 (2011) no. 10, pp. 3-18.

Voir la notice de l'article provenant de la source Math-Net.Ru

Problem of balanced distribution of mesh among processors arises in numerical solution on distributed memory systems of problems in computational fluid dynamics and computational mechanics. Parallel decomposition of triangular and tetrahedral meshes, containing up to $10^9$ vertices, is the aim of this research. Methods, realized in state-of-the-art parallel partitioning tools PARMETIS, JOSTLE, PT-SCOTCH and ZOLTAN, are based on multilevel algorithms that have a shortcoming of formation of unconnected domains. Second shortcoming of the most often used package PARMETIS is generation of strongly unbalanced results of mesh partitioning when partitioning on great number of domains, in particular formation of domains without vertices. Parallel incremental algorithm of graph partitioning and parallel geometric algorithm of mesh partitioning are developed on basis of the incremental algorithm of graph partitioning and the recursive coordinate bisection algorithm. The aim of development of these algorithms is generation of balanced partitioning of triangular and tetrahedral meshes, containing up to $10^9$ vertices, on great number of connected domains. According to these algorithms parallel partitioning tool for large mesh decomposition is created.
Keywords: mesh decomposition, graph partitioning. 
@article{MM_2011_23_10_a0,
     author = {E. N. Golovchenko},
     title = {Parallel partitioning tool for large mesh decomposition},
     journal = {Matemati\v{c}eskoe modelirovanie},
     pages = {3--18},
     publisher = {mathdoc},
     volume = {23},
     number = {10},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MM_2011_23_10_a0/}
}
TY  - JOUR
AU  - E. N. Golovchenko
TI  - Parallel partitioning tool for large mesh decomposition
JO  - Matematičeskoe modelirovanie
PY  - 2011
SP  - 3
EP  - 18
VL  - 23
IS  - 10
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MM_2011_23_10_a0/
LA  - ru
ID  - MM_2011_23_10_a0
ER  - 
%0 Journal Article
%A E. N. Golovchenko
%T Parallel partitioning tool for large mesh decomposition
%J Matematičeskoe modelirovanie
%D 2011
%P 3-18
%V 23
%N 10
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MM_2011_23_10_a0/
%G ru
%F MM_2011_23_10_a0
E. N. Golovchenko. Parallel partitioning tool for large mesh decomposition. Matematičeskoe modelirovanie, Tome 23 (2011) no. 10, pp. 3-18. http://geodesic.mathdoc.fr/item/MM_2011_23_10_a0/

[1] Walshaw C., Cross M., “Mesh Partitioning: A Multilevel Balancing and Refinement Algorithm”, SIAM J. Sci. Comput., 22:1 (2000), 63–80 | DOI | MR | Zbl

[2] Walshaw C., Cross M., “Parallel Mesh Partitioning on Distributed Memory Systems”, Invited lecture, Proc. Parallel and Distributed Computing for Computational Mechanics, Weimar, Cermany, 1999

[3] Schloegel K., Karypis G., Kumar V., “Graph Partitioning for High Performance Scientific Simulations”, CRPC Parallel Computing Handbook, Army HPC Research Center, Dept. of Computer Science and Engineering, University of Minnesota, Minneapolis, 2000

[4] Hendrickson B., Kolda T. G., “Graph partitioning models for parallel computing”, Parallel Computing, 26 (2000), 1519–1534 | DOI | MR | Zbl

[5] Karypis G., Kumar V., “A Parallel Algorithm for Multilevel Graph Partitioning and Sparse Matrix Ordering”, Journal of Parallel and Distributed Computing, 48 (1998), 71–95 | DOI

[6] Walshaw C., Cross M., “Parallel optimization algorithms for multilevel mesh partitioning”, Parallel Computing, 26 (2000), 1635–1660 | DOI | MR | Zbl

[7] Pellegrini F., “PT-Scotch and lib Scotch 5.1 User's Guide”, Bacchus team, INRIA Bordeaux Sud-Ouest, ENSEIRB and LaBRI, UMR CNRS 5800, Universite Bordeaux I,, Talence, France, 2010, 1–78

[8] Boman E., Devine K., Catalyurek U., Bozdag D., Hendrickson B., Mitchell W. F., Teresco J., Zoltan: Parallel Partitioning, Load Balancing and Data-Management Services, Developer's Guide, Version 3.3, Sandia National Laboratories, 2000–2010 http://www.cs.sandia.gov/Zoltan/dev_html/dev.html

[9] Yakobovskii M. V., “Inkrementnyi algoritm dekompozitsii grafov”, Vestnik Nizhegorodskogo universiteta im. N. I. Lobachevskogo. Seriya: Matematicheskoe modelirovanie i optimalnoe upravlenie, 2005, no. 1(28), 243–250

[10] Hendrickson B., Leland R., A Multilevel Algorithm for Partitioning Graphs, SAND 93-1301, Unlimited Release, 1993

[11] Preis R., Diekmann R., “PARTY – A Software Library for Graph Partitioning”, Advances in Computational Mechanics with Parallel and Distributed Processing, CIVIL-COMP PRESS, 1997, 63–71 | DOI

[12] Knut D. E., Iskusstvo programmirovaniya, 2-e izd., v. 3, Sortirovka i poisk, Izdatelskii dom “Vilyams”, M., 2001, per. s angliiskogo

[13] Yakobovskii M. V., “Parallelnye algoritmy sortirovki bolshikh ob'emov dannykh”, Fundamentalnye fiziko-matematicheskie problemy i modelirovanie tekhniko-tekhnologicheskikh sistem. Sb. nauch. tr., vypusk 7, ed. L. A. Uvarova, Yanus-K, M., 2004, 235–249

[14] Hendrickson B., Leland R., The Chaco User's Guide, Version 2.0, SAND 95-2344, Unlimited Release, 1995