Balanced Partitioning of Grids and Related Graphs. A Theoretical Study of Data Distribution in Parallel Finite Element Model Simulations

Andreas Emil Feldmann

ISBN 10: 3954041251 / ISBN 13: 9783954041251

Published by Cuvillier, 2012

About this Item

Balanced Partitioning of Grids and Related Graphs. A Theoretical Study of Data Distribution in Parallel Finite Element Model Simulations | Andreas Emil Feldmann | Taschenbuch | Kartoniert / Broschiert | Englisch | 2012 | Cuvillier | EAN 9783954041251 | Verantwortliche Person für die EU: preigu GmbH & Co. KG, Lengericher Landstr. 19, 49078 Osnabrück, mail[at]preigu[dot]de | Anbieter: preigu.

Seller Inventory # 121577438

Bibliographic Details

• Title: Balanced Partitioning of Grids and Related Graphs. A Theoretical Study of Data Distribution in Parallel Finite Element Model Simulations
• Publisher: Cuvillier
• Publication Date: 2012
• Language: English
• ISBN 10: 3954041251
• ISBN 13: 9783954041251
• Binding: Taschenbuch
• Condition: Neu
• Dimensions: 210W x 148H x 13D millimeters 210 millimeters width by 148 millimeters height by 13 millimeters depth
• Weight: 289 grams
• Seller catalogs:
  • Bücher

About this title

Synopsis

This thesis considers the k-BALANCED PARTITIONING problem, which is defined as follows. Find the minimum number of edges in a graph that, when cut, partition the vertices into k (almost) equally sized sets. Amongst others, the problem derives its importance from the need to distribute data within a parallel-computing architecture. In this setting we are particularly interested in 2D finite element model (FEM) simulations. We therefore model the input as a regular quadrilateral tiling of the plane. More precisely, we focus on solid grid graphs. These are finite connected subgraphs of the infinite 2D grid without holes. However we also consider other graph classes. In particular, trees often give surprising conclusions to the problem on grid graphs. We provide several efficient algorithms computing provably good solutions. For the case when k=2 (the BISECTION problem) these include methods to compute optimal as well as approximate solutions. When k can take arbitrary values we provide two kinds of approximation algorithms. First we give a method that is fast but, for practical applications, has unsatisfactory approximation ratios. Additionally we provide an algorithm computing near-optimal solutions, which however is too slow to be used in practice. We also prove that the gained tradeoff between fast runtime and good approximation factors is unavoidable. For this we provide corresponding hardness results.