publication . Article . Conference object . Preprint . Other literature type . 2008

PT-Scotch: A tool for efficient parallel graph ordering

Chevalier, Cédric; Pellegrini, François;
Open Access
  • Published: 01 Jul 2008 Journal: Parallel Computing, volume 34, pages 318-331 (issn: 0167-8191, Copyright policy)
  • Publisher: Elsevier BV
  • Country: France
Abstract
International audience; 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...
Subjects
free text keywords: Theoretical Computer Science, Computer Networks and Communications, Hardware and Architecture, Software, Artificial Intelligence, Computer Graphics and Computer-Aided Design, Heuristics, Nested dissection, Difficult problem, Implementation, Computer science, business.industry, business, Graph, Parallel computing, Multithreading, Slightly worse, sparse matrix ordering, [ INFO.INFO-DC ] Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC], Parallel graph ordering, Distributed memory computer, Multi-threading, Computer Science - Distributed, Parallel, and Cluster Computing
31 references, page 1 of 3

1. MeTiS: Family of multilevel partitioning algorithms, http://glaros.dtc.umn.edu/ gkhome/views/metis.

2. Jostle: Graph partitioning software, http://staffweb.cms.gre.ac.uk/~c. walshaw/jostle/.

3. Scotch: Static mapping, graph partitioning, and sparse matrix block ordering package, http://www.labri.fr/~pelegrin/scotch/.

4. W. F. Tinney, J. W. Walker, Direct solutions of sparse network equations by optimally ordered triangular factorization, J. Proc. IEEE 55 (1967) 1801-1809.

5. P. Amestoy, T. Davis, I. Duff, An approximate minimum degree ordering algorithm, SIAM J. Matrix Anal. and Appl. 17 (1996) 886-905.

6. A. George, J. W.-H. Liu, The evolution of the minimum degree ordering algorithm, SIAM Review 31 (1989) 1-19.

7. J. W.-H. Liu, Modification of the minimum-degree algorithm by multiple elimination, ACM Trans. Math. Software 11 (2) (1985) 141-153.

8. T.-Y. Chen, J. R. Gilbert, S. Toledo, Toward an efficient column minimum degree code for symmetric multiprocessors, in: Proc. 9th SIAM Conf. on Parallel Processing for Scientific Computing, San-Antonio, 1999.

9. J. A. George, J. W.-H. Liu, Computer solution of large sparse positive definite systems, Prentice Hall, 1981.

10. F. Pellegrini, J. Roman, P. Amestoy, Hybridizing nested dissection and halo approximate minimum degree for efficient sparse matrix ordering, Concurrency: Practice and Experience 12 (2000) 69-84.

11. S. T. Barnard, H. D. Simon, A fast multilevel implementation of recursive spectral bisection for partitioning unstructured problems, Concurrency: Practice and Experience 6 (2) (1994) 101-117.

12. B. Hendrickson, R. Leland, A multilevel algorithm for partitioning graphs, in: Proceedings of Supercomputing, 1995. [OpenAIRE]

13. G. Karypis, V. Kumar, A fast and high quality multilevel scheme for partitioning irregular graphs, SIAM Journal on Scientific Computing 20 (1) (1998) 359-392.

14. B. W. Kernighan, S. Lin, An efficient heuristic procedure for partitionning graphs, BELL System Technical Journal (1970) 291-307.

15. C. M. Fiduccia, R. M. Mattheyses, A linear-time heuristic for improving network partitions, in: Proc. 19th Design Automation Conference, IEEE, 1982, pp. 175-181. [OpenAIRE]

31 references, page 1 of 3
Powered by OpenAIRE Open Research Graph
Any information missing or wrong?Report an Issue
publication . Article . Conference object . Preprint . Other literature type . 2008

PT-Scotch: A tool for efficient parallel graph ordering

Chevalier, Cédric; Pellegrini, François;