meDDec




 Leonidas Linardakis

 Department of Computer Science
College of William and Mary





Description
The meDDec package produces uniform and graded domain decompositions suitable for generating large Delaunay meshes for 2-dimensional geometries. The decompositions are created using the Medial Axis Domain Decomposition algorithm, and the meshes can be generated independently for each subdomain due to the uniform Delaunay Decoupling procedure and the graded Delaunay Decoupling procedure.  The  gradation of the decomposition and of the mesh can be controlled using either a background mesh or an area sizing function.  These decompositions can be used by parallel mesh generators to create very large meshes, of the order of billions of elements, or by sequential meshers to create large meshes, of the order of tens of millions of elements.


Results
Sequential Experiments
Decomposition (meDDec) Mesh Generation (Triangle)
Domain Mesh Type #Processors
 #Subdomains
 Time
 #Triangles
 Time
CBay
 uniform 1
 71
 1.0 sec.
 50 M
 77 sec.
Pipe uniform 1 64 0.2 sec. 50 M 75 sec.
Pipe
 graded(sources) 1
 837
 1.3 sec
 50 M
 79 sec.
Pipe
 graded(mesh) 1
 203
 0.5 sec
 50 M
 75 sec.

Parallel Experiments
Decomposition (meDDec)
 Mesh Generation (Triangle)
Domain Mesh Type #Processors #Subdomains
 Time
 #Triangles
 Time
CBay
 uniform 144
 4440
 16 sec.
 5.2 B
 130 sec.
Pipe uniform 144 4319
  14 sec. 5.2 B 129 sec.
Pipe
 graded(sources) 144
 4518 14 sec
 5.1 B
 130 sec.
Pipe
 graded(mesh) 144
 4343
 13 sec
 5.1 B
 129 sec.





The sequential experiments were performed on a Pentium IV Xeon 3.06GHz processor with 2GB RAM, while the parallel experiments were performed on Sciclone using the vortex, twister and whirlwind subclusters. The times do not include the file IO. Triangle was used as the mesh generation library. The CBay domain is a model of the Chesapeake bay and it includes 13,524 segments and 26 islands. The Pipe domain is an approximation of a cross section of a rocket geometry and it consists from 576 boundary segments and 9 holes.

Download

meDDec is written in c99 standard C and uses the Triangle library to create the Delaunay triangulations and meshes, and the Metis library for graph partitioning.  Before you install meDDec you need to download and compile (make all) these libraries. You can download the meDDec source code here.  The parallel mesh generation version of meDDec (pmeDDec) for distributed memory environments is avaliable here.  It is implemented using standard MPI (I have tested using LAM/MPI on a Solaris system).  The Triangle library is used as an off-the-shelf mesh generator.

I'll be glad to hear from you if you use meDDec, email me at lxlina@wm.edu.

Credits

The meDDec software makes use of two state-of-art libraries:  Triangle, created by Jonathan Richard Shewchuk, and Metis, created by George Karypis and his group. The good performance of meDDec is based on the performance of these two libraries. The pictures were produced using the very handy mview.