Título: | A Round-Robin Parallel Partitioning Algorithm |
Autores: | Moore, Doug W. |
Fecha: |
2007-04-23 2007-04-23 1988-06 |
Publicador: | Cornell University |
Fuente: |
Ver documento Ver documento |
Tipo: | Technical Report |
Tema: |
computer science technical report |
Descripción: | We develop parallel heuristic algorithms for partitioning the vertices of a graph into many groups of roughly equal size so that few edges connect vertices in different groups. The algorithms are intended for a message passing multiprocessor such as a hypercube, but only require the processors to be connected as a ring. They are based on the Kernighan-Lin algorithm, which finds a small edge separator that divides a graph into two pieces of equal size. Each of the algorithms features a parameter that allows for a trade-off between the potentially conflicting goals of reducing the number of edges between different groups and keeping the sizes of the groups roughly the same. These algorithms are applied to the problem of parallel block oriented Cholesky factorization. For an efficient factorization, we need a graph partition in which few pairs of vertex groups are interconnected; that is, we desire the quotient graph induced by the partition to be sparse. We discuss how standard partitioning heuristics may fail to give sparse quotient graphs and how they can be modified to correct this. |
Idioma: | Inglés |
1 Dance in the Noh Theater, Volume 1: Dance Analysis por Bethe, Monica,Brazell, Karen | 6 Rationality and Reason Today por Welsch, Wolfgang |
2 Dance in the Noh Theater, Volume 3: Dance Patterns por Bethe, Monica,Brazell, Karen | 7 Reason: traditional and contemporary, or Why should we still speak of reason at all? por Welsch, Wolfgang |
3 Archives or Assets? por Hirtle, Peter B. | 8 High Precision Lattice QCD: Perturbations in a Non-Perturbative World por Mason, Quentin |
4 Digital Preservation and Copyright por Hirtle, Peter B. | 9 Unpublished Materials, New Technologies, and Copyright: Facilitating Scholarly Use por Hirtle, Peter B. |
5 Reason and Transition: On the Concept of Transversal Reason por Welsch, Wolfgang | 10 |