Parallel mesh generation

From Wikipedia, the free encyclopedia

 This article or section needs to be wikified to meet Wikipedia's quality standards.
Please help improve this article with relevant internal links. (September 2007)

Parallel mesh generation in numerical analysis is a new research area between the boundaries of two scientific computing disciplines: computational geometry and parallel computing[1]. Parallel mesh generation methods decompose the original mesh generation problem into smaller subproblems which are solved (meshed) in parallel using multiple processors or threads. The existing parallel mesh generation methods can be classified in terms of two basic attributes: (1) the sequential technique used for meshing the individual subproblems and (2) the degree of coupling between the subproblems. One of the challenges in parallel mesh generation is to develop parallel meshing software using off-the-shelf sequential meshing codes.

[edit] Overview

Parallel mesh generation procedures in general decompose the original 2-dimensional (2D) or 3-dimensional (3D) mesh generation problem into N smaller subproblems which are solved (i.e., meshed) concurrently using P processors or threads[1]. The subproblems can be formulated to be either tightly coupled[2][3], partially coupled[4][5] or even decoupled[6][7]. The coupling of the subproblems determines the intensity of the communication and the amount/type of synchronization required between the subproblems.

The challenges in parallel mesh generation methods are: to maintain stability of the parallel mesher (i.e., retain the quality of finite elements generated by state-of-the-art sequential codes) and at the same time achieve 100% code re-use (i.e., leverage the continuously evolving and fully functional off-the-shelf sequential meshers) without substantial deterioration of the scalability of the parallel mesher.

There is a difference between parallel mesh generation and parallel triangulation. In parallel triangulation a pre-defined set of points is used to generate in parallel triangles that cover the convex hull of the set of points. A very efficient algorithm for parallel Delaunay triangulations appears in Blelloch et al.[8]. This algorithm is extended in Clemens and Walkington[9] for parallel mesh generation.

[edit] Parallel mesh generation software

While many solvers have been ported to parallel machines, grid generators have left behind. Still the preprocessing step of mesh generation remains a sequential bottleneck in the simulation cycle. That is why the need for developing of stable 3D parallel grid generator is well-justified. Work in this direction is carried out by several institutions [10]. parTgen[11] - partitioner and parallel tetrahedral mesh generator is an example of decoupled method developed and implemented by Ivanov et al.[12] [13]

[edit] References

  1. ^ a b Nikos Chrisochoides, Parallel Mesh Generation, Chapter in Numerical Solution of Partial Differential Equations on Parallel Computers, (Eds. Are Magnus Bruaset, Aslak Tveito), Springer-Verlag, pp 237-259, 2005.
  2. ^ Nikos Chrisochoides and Demian Nave. Parallel Delaunay mesh generation kernel. Int. J. Numer. Meth. Engng., 58:161--176, 2003
  3. ^ Lohner, J.Camberos, and M.Marshal. Parallel Unstructured Grid Generation. Chapter in Unstructured Scientific Computation on Scalable Multiprocessors. (Eds. Piyush Mehrotra and Joel Saltz), pp 31--64, MIT Press, 1990.
  4. ^ H. de Cougny and M.Shephard. Parallel volume meshing using face removals and hierarchical repartitioning. Comp. Meth. Appl. Mech. Engng., 174(3-4):275--298, 1999.
  5. ^ Andrey Chernikov and Nikos Chrisochoides. Parallel Guaranteed Quality Planar Delaunay Mesh Refinement Concurrent Point Insertion. SIAM Journal for Scientific Computing, Vol. 28, No. 5, pp 1907-1926, 2006.
  6. ^ J. Galtier and P. L. George. Prepartitioning as a way to mesh subdomains in parallel. Special Symposium on Trends in Unstructured Mesh Generation, pp 107--122. ASME/ASCE/SES, 1997.
  7. ^ Leonidas Linardakis and Nikos Chrisochoides. Delaunay Decoupling Method for Parallel Guaranteed Quality Planar Mesh Generation. SIAM Journal for Scientific Computing, Vol. 27, No. 4, pp 1394-1423, 2006.
  8. ^ G. E. Blelloch, J.C. Hardwick, G.~L. Miller, and D. Talmor, Design and implementation of a practical parallel Delaunay algorithm, Algorithmica, 24 (1999), pp. 243--269.
  9. ^ Clemens Kadow and Noel Walkington. Design of a projection-based parallel Delaunay mesh generation and refinement algorithm. In proceedings of Fourth Symposium on Trends in Unstructured Mesh Generation, 2003.
  10. ^ Fraunhofer Institute for Industrial Mathematics, http://www.itwm.fhg.de
  11. ^ parTgen - partitioner and parallel tetrahedral mesh generator, http://www.itwm.fhg.de/en/hpc__partgen/partgen/
  12. ^ E.G. Ivanov, H. Andrae and A.N. Kudryavtsev, Domain Decomposition Approach for Automatic Parallel Generation of Tetrahedral Grids, International Mathematical Journal Computational Methods in Applied Mathematics, Vol.6(2), 2006, pp. 178--193.
  13. ^ E. Ivanov, O. Gluchshenko, H. Andrae, A. Kudryavtsev, Automatic Parallel Generation of Tetrahedral Grids by Using a Domain Decomposition Approach, Journal of Computational Mathematics and Mathematical Physics, Vol. 48(8), 2008, pp. 1-10