Parallel mesh generation: Difference between revisions

Revision as of 14:33, 25 September 2007

Revision as of 03:54, 10 October 2007

Line 1:

{{Wikify|date=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]]<ref name="Chrisochoides">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.</ref>. 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.

Parallel mesh generation in [[numerical analysis]] is 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.

==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<ref name="Chrisochoides"/>. The subproblems can be formulated to be either tightly coupled<ref>Nikos Chrisochoides and Demian Nave. Parallel [[Delaunay]] mesh generation kernel. Int. J. Numer. Meth. Engng., 58:161--176, 2003</ref><ref>Lohner, J.Camberos, and M.Marshal. Parallel Unstructured Grid

Parallel mesh generation procedures in general decompose the original

Generation. Chapter in Unstructured Scientific Computation on Scalable Multiprocessors. (Eds. Piyush Mehrotra and Joel Saltz), pp 31--64, MIT Press, 1990.</ref>, partially coupled<ref>H. de Cougny and M.Shephard. Parallel volume meshing using face removals and hierarchical repartitioning. Comp. Meth. Appl. Mech. Engng.,

2-dimensional (2D) or 3-dimensional (3D) mesh generation problem into

174(3-4):275--298, 1999.</ref><ref>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.</ref> or even decoupled<ref>J. Galtier and P. L. George. Prepartitioning as a way to mesh

N smaller subproblems which are solved (i.e., meshed) concurrently

subdomains in parallel. Special Symposium on Trends in Unstructured Mesh Generation, pp 107--122. ASME/ASCE/SES, 1997.</ref><ref>Leonidas Linardakis and Nikos Chrisochoides. Delaunay Decoupling Method for Parallel Guaranteed Quality Planar Mesh Generatiion. SIAM Journal for Scientific Computing, Vol. 27, No. 4, pp 1394-1423, 2006.</ref>. The coupling of the subproblems determines the intensity of the communication and the amount/type of synchronization required between the subproblems.

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.

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.<ref>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.</ref>. This algorithm is extended in Clemens and Walkington<ref>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.</ref> for parallel mesh generation.

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 [8]. This algorithm is extended

in [9] for parallel mesh generation.

==References==

<references/>

[1] 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 Generatiion. 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.

[[Category:Numerical differential equations]]