To solve the graph partitioning problem, ef.cient heuristics have been developed that are also capable of distributing the computational load in parallel FEM computations. However, although a few parallel implementations do exist, the involved algorithms are hard to parallelize due to their sequential nature. This paper presents a new approach to deal with the FEM graph partitioning problem. Applying diffusion as a growing mechanism, we are able to eliminate restrictions of former implementations based on the bubble framework and construct a relatively simple algorithm with a high degree of "natural" parallelism. We demonstrate that it computes solutions comparable to those of established heuristics. Its drawback is the long execution time if the parallelism is not exploited.
Index Terms:
FEM graph partitioning, load balancing, diffusion, first-order-scheme, bubble
Citation:
Stefan Schamberger, "On Partitioning FEM Graphs Using Diffusion," ipdps, vol. 18, pp.277b, 18th International Parallel and Distributed Processing Symposium (IPDPS'04) - Workshop 17, 2004