Parallel mesh generation

Last updated

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:

Contents

  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.

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.

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.

A parallel version of the MeshSim mesh generator by Simmetrix Inc., [10] is available for both research and commercial use. It includes parallel implementations of surface, volume and boundary layer mesh generation as well as parallel mesh adaptivity. The algorithms it uses are based on those in reference [4] and are scalable (both in the parallel sense and in the sense that they give speedup compared to the serial implementation) and stable. For multicore or multiprocessor systems, there is also a multithreaded version of these algorithms that are available in the base MeshSim product [11]

Another parallel mesh generator is D3D, [12] was developed by Daniel Rypl [13] at Czech Technical University in Prague. D3D is a mesh generator capable to discretize in parallel (or sequentially) 3D domains into mixed meshes.

BOXERMesh [14] is an unstructured hybrid mesh generator [15] developed by Cambridge Flow Solutions. [16] Implemented as distributed-memory fully parallelised software, it is specifically designed to overcome the traditional bottlenecks constraining engineering simulation, delivering advanced meshing on geometries of arbitrary complexity and size. Its scalability has been demonstrated on very large meshes generated on HPC clusters.

Challenges in parallel mesh generation

It takes substantial time to develop the algorithmic and software infrastructure for commercial sequential mesh generation libraries. Moreover, improvements in terms of quality, speed, and functionality are open ended which makes the task of creating leading edge parallel mesh generation codes challenging.

An area with immediate high benefits to parallel mesh generation is domain decomposition. The DD problem as it is posed in [17] is still open for 3D geometries and its solution will help to deliver stable and scalable methods that rely on off-the-shelf mesh generation codes for Delaunay and Advancing Front Techniques.

Finally, a long term investment to parallel mesh generation is to attract the attention of mathematicians with open problems in mesh generation and broader impact in mathematics.

See also

Related Research Articles

<span class="mw-page-title-main">Delaunay triangulation</span> Triangulation method named after Boris Delaunay

In mathematics and computational geometry, a Delaunay triangulation for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle of any triangle in DT(P). Delaunay triangulations maximize the minimum of all the angles of the triangles in the triangulation; they tend to avoid sliver triangles. The triangulation is named after Boris Delaunay for his work on this topic from 1934.

In computer science, a parallel algorithm, as opposed to a traditional serial algorithm, is an algorithm which can do multiple operations in a given time. It has been a tradition of computer science to describe serial algorithms in abstract machine models, often the one known as random-access machine. Similarly, many computer science researchers have used a so-called parallel random-access machine (PRAM) as a parallel abstract machine (shared-memory).

Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational geometry. While modern computational geometry is a recent development, it is one of the oldest fields of computing with a history stretching back to antiquity.

<span class="mw-page-title-main">Voronoi diagram</span> Type of plane partition

In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. In the simplest case, these objects are just finitely many points in the plane. For each seed there is a corresponding region, called a Voronoi cell, consisting of all points of the plane closer to that seed than to any other. The Voronoi diagram of a set of points is dual to that set's Delaunay triangulation.

In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.

In geometry, a triangulation is a subdivision of a planar object into triangles, and by extension the subdivision of a higher-dimension geometric object into simplices. Triangulations of a three-dimensional volume would involve subdividing it into tetrahedra packed together.

Numerical methods for partial differential equations is the branch of numerical analysis that studies the numerical solution of partial differential equations (PDEs).

<span class="mw-page-title-main">Mesh generation</span> Subdivision of space into cells

Mesh generation is the practice of creating a mesh, a subdivision of a continuous geometric space into discrete geometric and topological cells. Often these cells form a simplicial complex. Usually the cells partition the geometric input domain. Mesh cells are used as discrete local approximations of the larger domain. Meshes are created by computer algorithms, often with human guidance through a GUI, depending on the complexity of the domain and the type of mesh desired. A typical goal is to create a mesh that accurately captures the input domain geometry, with high-quality (well-shaped) cells, and without so many cells as to make subsequent calculations intractable. The mesh should also be fine in areas that are important for the subsequent calculations.

In computational geometry, the Bowyer–Watson algorithm is a method for computing the Delaunay triangulation of a finite set of points in any number of dimensions. The algorithm can be also used to obtain a Voronoi diagram of the points, which is the dual graph of the Delaunay triangulation.

In mesh generation, Delaunay refinement are algorithms for mesh generation based on the principle of adding Steiner points to the geometry of an input to be meshed, in a way that causes the Delaunay triangulation or constrained Delaunay triangulation of the augmented input to meet the quality requirements of the meshing application. Delaunay refinement methods include methods by Chew and by Ruppert.

Dantzig–Wolfe decomposition is an algorithm for solving linear programming problems with special structure. It was originally developed by George Dantzig and Philip Wolfe and initially published in 1960. Many texts on linear programming have sections dedicated to discussing this decomposition algorithm.

In computational geometry, a constrained Delaunay triangulation is a generalization of the Delaunay triangulation that forces certain required segments into the triangulation as edges, unlike the Delaunay triangulation itself which is based purely on the position of a given set of vertices without regard to how they should be connected by edges. It can be computed efficiently and has applications in geographic information systems and in mesh generation.

TetGen is a mesh generator developed by Hang Si which is designed to partition any 3D geometry into tetrahedrons by employing a form of Delaunay triangulation whose algorithm was developed by the author.

Grids or meshes are geometrical shapes which are small-sized discrete cells that cover the physical domain, whose objective is to identify the discrete volumes or elements where conservation laws can be applied. They have applications in the fields of computational fluid dynamics (CFD), geography, designing and many more places where numerical solutions to the partial differential equations (PDEs) are required.

MoFEM is an open source finite element analysis code developed and maintained at the University of Glasgow. MoFEM is tailored for the solution of multi-physics problems with arbitrary levels of approximation, different levels of mesh refinement and optimised for high-performance computing. MoFEM is the blend of the Boost MultiIndex containers, MOAB and PETSc. MoFEM is developed in C++ and it is open-source software under the GNU Lesser General Public License (GPL).

<span class="mw-page-title-main">Surface triangulation</span> Partition of a surface into a net of triangles

Triangulation of a surface means

References

  1. 1 2 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. 1 2 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. ↑ "Parallel MeshSim". Archived from the original on 2009-02-18. Retrieved 2009-08-05.
  11. ↑ "MeshSim". Archived from the original on 2009-09-27. Retrieved 2009-08-05.
  12. ↑ D3D Mesh Generator Web page
  13. ↑ University Web page of Daniel Rypl, http://mech.fsv.cvut.cz/~dr/
  14. ↑ BOXERMesh
  15. ↑ Scalable Parallel Mesh Generation
  16. ↑ Cambridge Flow Solutions
  17. ↑ Chrisochoides N., A Survey of Parallel Mesh Generation Methods, Brown University, Providence RI - 2005.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.