A parallelisable multi-level banded diffusion scheme for computing balanced partitions with smooth boundaries
PELLEGRINI, François
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithms and high performance computing for grand challenge applications [SCALAPPLIX]
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithms and high performance computing for grand challenge applications [SCALAPPLIX]
PELLEGRINI, François
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithms and high performance computing for grand challenge applications [SCALAPPLIX]
< Reduce
Laboratoire Bordelais de Recherche en Informatique [LaBRI]
Algorithms and high performance computing for grand challenge applications [SCALAPPLIX]
Language
en
Communication dans un congrès
This item was published in
Euro-Par 2007 Parallel Processing, Euro-Par 2007 Parallel Processing, EuroPar, 2007-08-28, Rennes. 2007-08, vol. 4641, p. 195-204
Springer
English Abstract
Graph partitioning algorithms have yet to be improved, because graph-based local optimization algorithms do not compute smooth and globally-optimal frontiers, while global optimization algorithms are too expensive to be ...Read more >
Graph partitioning algorithms have yet to be improved, because graph-based local optimization algorithms do not compute smooth and globally-optimal frontiers, while global optimization algorithms are too expensive to be of practical use on large graphs. This paper presents a way to integrate a global optimization, diffusion algorithm in a banded multi-level framework, which dramatically reduces problem size while yielding balanced partitions with smooth boundaries. Since all of these algorithms do parallelize well, high-quality parallel graph partitioners built using these algorithms will have the same quality as state-of-the-art sequential partitionersRead less <
English Keywords
graph partitioning
band
diffusion
aspect ratio
jug
danaides
ANR Project
SOLveurs et SimulaTIons en Calculs Extrême - ANR-06-CIS6-0010
Origin
Hal imported