PARS -- Adaptive Mesh Refinement

Scalable libraries for parallel, adaptive mesh refinement

Many scientific applications have the property that the solution changes rapidly in small areas of the total domain being modeled. In order to efficiently solve these problems, adaptive mesh strategies are used to concentrate grid points in regions where the error contribution is large. In this way, one can improve the quality of the approximate solution while keeping the total number of grid points small.

Click here for a movie demonstrating adaptive refinement.

We have developed scalable libraries for parallel, adaptive mesh refinement on two-dimensional triangular grids. This general-purpose software uses bisection of the longest edge to refine and de-refine triangles in conjunction with Rivara's technique for removing nonconforming points from the mesh. To refine triangles in parallel, we use independent sets of elements as determined by the dual graph of the mesh. This technique guarantees that duplicate vertices are not created and that data coherence is maintained across processors. The parallel execution time of this algorithm is determined only by the number of marked triangles and the number of levels of propagation of refinement.

The adaptive mesh generated by the strategy described above must be repartitioned after each modification to achieve good load balancing on parallel computers. To accomplish this task, we have developed a new geometric partitioning algorithm that strives to minimize both latency and transmission communication costs on distributed-memory computers. This partitioning heuristic, which we call unbalanced recursive bisection, uses the geometric location of the mesh nodes to generate a partition tree. It is often not necessary to calculate a new partition tree with every modification of the mesh. The software shifts the partition boundaries as long as the partition aspect ratios remain acceptable; otherwise, it computes a new partition tree.

This software is portable and uses the MPI message-passing standard. Computational results have been obtained for a wide variety of architectures including the IBM SP series, Intel DELTA and Paragon, the Cray T3D, and networks of SUN, SGI, HP, DEC alpha, and IBM RS/6000 workstations.

This software is currently under development at Argonne National Laboratory and the University of Tennessee and is available for use in research projects. These algorithms are currently being extended to three-dimensional domains discretized into tetrahedron.

Previous: Mesh Smoothing
Next: Mesh Partitioning
Back: Unstructured Mesh Home Page