# Parallel mesh partitioning on distributed memory systems

Walshaw, C. and Cross, M.
(2002)
*Parallel mesh partitioning on distributed memory systems.*
In: Topping, B.H.V., (ed.)
Computational Mechanics using High Performance Computing.
Computational Science, Engineering & Technology
(9).
Saxe-Coburg Publications, Kippen, Stirling, Scotland, pp. 59-78.
ISBN 1874672075
(doi:10.4203/csets.9.3)

## Abstract

The problem of deriving parallel mesh partitioning algorithms for mapping unstructured meshes to parallel computers is discussed in this chapter. In itself this raises a paradox - we seek to find a high quality partition of the mesh, but to compute it in parallel we require a partition of the mesh. In fact, we overcome this difficulty by deriving an optimisation strategy which can find a high quality partition even if the quality of the initial partition is very poor and then use a crude distribution scheme for the initial partition. The basis of this strategy is to use a multilevel approach combined with local refinement algorithms. Three such refinement algorithms are outlined and some example results presented which show that they can produce very high global quality partitions, very rapidly. The results are also compared with a similar multilevel serial partitioner and shown to be almost identical in quality. Finally we consider the impact of the initial partition on the results and demonstrate that the final partition quality is, modulo a certain amount of noise, independent of the initial partition.

Item Type: | Book Section |
---|---|

Additional Information: | [1] Chapter 3. [2] Computational Science, Engineering & Technology Series ISSN: 1759-3158. [3] CMS Ref. No: 02/57. |

Uncontrolled Keywords: | parallel mesh partitioning algorithms, parallel computers, algorithms, distributed memory systems, final partition |

Subjects: | Q Science > QA Mathematics > QA76 Computer software |

Pre-2014 Departments: | School of Computing & Mathematical Sciences School of Computing & Mathematical Sciences > Centre for Numerical Modelling & Process Analysis School of Computing & Mathematical Sciences > Centre for Numerical Modelling & Process Analysis > Computational Science & Engineering Group School of Computing & Mathematical Sciences > Computer & Computational Science Research Group School of Computing & Mathematical Sciences > Department of Computer Science School of Computing & Mathematical Sciences > Department of Mathematical Sciences |

Related URLs: | |

Last Modified: | 14 Oct 2016 09:01 |

URI: | http://gala.gre.ac.uk/id/eprint/627 |

### Actions (login required)

View Item |