Title: An improved spectral bisection algorithm and its application to dynamic load balancing
Authors: Vandriessche, R ×
Roose, Dirk #
Issue Date: Jan-1995
Publisher: Elsevier science bv
Series Title: Parallel computing vol:21 issue:1 pages:29-48
Abstract: The efficient parallel execution of grid-oriented scientific calculations requires a partitioning of the grid that minimises both load imbalance and interprocessor communication. For unstructured static grids, good partitions are obtained with the recursive spectral bisection heuristic, applied to the interdependency graph of the grid. We will describe an alternative spectral bisection algorithm that yields better partitions than the standard algorithm, especially for interdependency graphs with a large variation in the weights of the edges. We will further describe how even in case of dynamically changing grids, grid-oriented problems can be formulated as graph partitioning problems for the purpose of load balancing. We will then partition these dynamically changing grids with the alternative spectral algorithm.
ISSN: 0167-8191
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Numerical Analysis and Applied Mathematics Section
× corresponding author
# (joint) last author

Files in This Item:

There are no files associated with this item.

Request a copy


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science