PT-Scotch swMATH ID: 7038 Software Authors: C. Chevalier; F. Pellegrini Description: PT-Scotch: A tool for efficient parallel graph ordering. The parallel ordering of large graphs is a difficult problem, because on the one hand minimum degree algorithms do not parallelize well, and on the other hand the obtainment of high quality orderings with the nested dissection algorithm requires efficient graph bipartitioning heuristics, the best sequential implementations of which are also hard to parallelize. This paper presents a set of algorithms, implemented in the PT-Scotch software package, which allows one to order large graphs in parallel, yielding orderings the quality of which is only slightly worse than the one of state-of-the-art sequential algorithms. Our implementation uses the classical nested dissection approach but relies on several novel features to solve the parallel graph bipartitioning problem. Thanks to these improvements, PT-Scotch produces consistently better orderings than ParMeTiS on large numbers of processors. Homepage: http://arxiv.org/abs/0907.1375 Keywords: Parallel graph ordering; Parallel nested dissection; Distributed-memory computer; Multi-threading Related Software: ParMETIS; PETSc; FreeFem++; Zoltan; METIS; p4est; Gmsh; SparseMatrix; Scotch; FEniCS; MUMPS; OpenFOAM; deal.ii; DibaP; Trilinos; GitHub; Peano; SIERRA; Python; SuperLU Cited in: 56 Publications all top 5 Cited by 172 Authors 4 Nataf, Frédéric 4 Tournier, Pierre-Henri 3 Burstedde, Carsten 3 Hecht, Frédéric 3 Holke, Johannes 3 Jolivet, Pierre 2 Agullo, Emmanuel 2 Badia, Santiago 2 Darve, Eric 2 Dolean, Victorita 2 Feldmann, Andreas Emil 2 Fournier, Yvan 2 Giraud, Luc 2 Hager, Georg 2 Houzeaux, Guillaume 2 Lin, Lin 2 Meyerhenke, Henning 2 Moxey, David 2 Sayah, Toni 2 Spillane, Nicole 2 Vassilevski, Panayot Spirov 2 Vazquez, Mariano 2 Wellein, Gerhard 2 Yang, Chao 1 Afanasiev, Michael 1 Aldbaissy, Rim 1 Allaire, Grégoire 1 Alvermann, Andreas 1 Amici, Roman 1 Arsaev, M. 1 Asner, Liya 1 Aykanat, Cevdet 1 Basermann, Achim 1 Benk, Janos 1 Böhm, Christian 1 Bollhöfer, Matthias 1 Boman, Erik G. 1 Bonelle, Jérôme 1 Borrell, Ricard 1 Bretto, Alain 1 Cajas, Juan Carlos 1 Cambier, Léopold 1 Cardiff, Philip 1 Castonguay, Patrice 1 Çatalyürek, Ümit V. 1 Chen, Chao 1 Cookson, A. N. 1 Daas, Hussam Al 1 Dabrowski, Marcin 1 Dapogny, Charles 1 de Hoop, Maarten V. 1 DeHart, Mark D. 1 Delling, Daniel 1 Delmas, Vincent 1 Demouth, Julien 1 Denk, Georg 1 Ducournau, Aurélien 1 E, Weinan 1 Fehske, Holger 1 Feppon, Florian 1 Fichtner, Andreas 1 Fleischman, Daniel 1 Gaston, Derek R. 1 Gharti, Hom Nath 1 Giraldo, Francis X. 1 Goldberg, Andrew V. 1 Gorobets, Andrey V. 1 Grigori, Laura 1 Grote, Marcus J. 1 Guermouche, Abdou 1 Gullapalli, Kiran 1 Haddad, Mireille 1 Hamm, Steve 1 Hapla, Vaclav 1 Harness, Yuval 1 Hauret, Patrice 1 Havé, Pascal 1 Horáček, Jaromir 1 Ivankovic, A. 1 Jacquelin, Mathias 1 Janalik, Radim 1 Jorba, Oriol 1 Karač, A. 1 Kayaaslan, Enver 1 Kelly, James F. 1 Kerfoot, E. 1 Kirby, Mike 1 Kirby, Robert M. II 1 Knapp, David 1 Knepley, Matthew G. 1 Komatitsch, Dimitri 1 Kong, Fande 1 Kopera, Michal A. 1 Koric, Seid 1 Kowalski, Julia 1 Kozinov, Evgeny 1 Krasnopolsky, Boris I. 1 Kreutzer, Moritz 1 Krischer, Lion 1 Krotkiewski, Marcin ...and 72 more Authors all top 5 Cited in 28 Serials 16 SIAM Journal on Scientific Computing 4 Computers and Fluids 3 Journal of Computational Physics 2 Computers & Mathematics with Applications 2 Computer Methods in Applied Mechanics and Engineering 2 International Journal for Numerical Methods in Engineering 2 SIAM Journal on Matrix Analysis and Applications 1 ACM Transactions on Mathematical Software 1 Numerische Mathematik 1 SIAM Journal on Numerical Analysis 1 Theoretical Computer Science 1 Parallel Computing 1 Algorithmica 1 Journal of Scientific Computing 1 Numerical Algorithms 1 Computational Mathematics and Mathematical Physics 1 International Journal of Computer Mathematics 1 Pattern Recognition 1 Mathematical Programming. Series A. Series B 1 ETNA. Electronic Transactions on Numerical Analysis 1 International Journal of Computational Fluid Dynamics 1 Optimization Methods & Software 1 Computational Geosciences 1 Archives of Computational Methods in Engineering 1 Comptes Rendus. Mécanique. Académie des Sciences, Paris 1 Journal of Numerical Mathematics 1 Lecture Notes in Computational Science and Engineering 1 Journal of Mathematics in Industry all top 5 Cited in 15 Fields 39 Numerical analysis (65-XX) 12 Fluid mechanics (76-XX) 11 Combinatorics (05-XX) 11 Computer science (68-XX) 8 Partial differential equations (35-XX) 4 Mechanics of deformable solids (74-XX) 3 Linear and multilinear algebra; matrix theory (15-XX) 2 Geophysics (86-XX) 2 Biology and other natural sciences (92-XX) 1 Optics, electromagnetic theory (78-XX) 1 Classical thermodynamics, heat transfer (80-XX) 1 Statistical mechanics, structure of matter (82-XX) 1 Operations research, mathematical programming (90-XX) 1 Systems theory; control (93-XX) 1 Information and communication theory, circuits (94-XX) Citations by Year