Parallel Mesh Smoothing
Parallel Mesh Smoothing
We propose a low-cost local optimization technique that guarantees improved mesh quality. We adjust grid point location in a local submesh consisting of the elements incident to the vertex to be smoothed by maximizing or minimizing a mesh quality measure that's expressed as an analytic function of grin point location. There are several mesh quality indicators that can be expressed in this way including element angle size and element aspect ratio. Any of these indicators can be used within the framework of our proposed technique. In this example we consider maximizing the minimum angle of the submesh, where the angle is expressed as a function of grid point location using the law of cosines.
The local solution space we consider is contained by the union of elements that are incident to the vertex. As the location of the vertex changes in the solution space, the minimum angle in the corresponding submesh is given by a nonsmooth composite function that is nondifferentiable at any point where the set of angles that achieve a minimum value changes. We formulate this as a nonsmooth optimization problem which is solved using an analogue of the steepest descent method for smooth functions. The initial step size for each iteration is chosen by predicting the points at which the active set changes using the gradient information available.
The effectiveness of the optimization algorithm is illustrated by examining the upper right quadrant of a rectangular domain with a hole. The mesh on the left is generated by recursively refining the initial mesh with no adjustment in grid point location after each refinement step. The global minimum angle in this mesh is 11.3 degrees and the average minimum element angle is 35.7 degrees. In addition, bisection lines from the coarse mesh are still clearly evident after many levels of refinement. By contrast, the mesh on the right was obtained by adjusting grid point location after each refinement step. The bisection lines are no longer evident and the elements in the mesh are less distorted. The global minimum angle in this mesh is 21.7 degrees and the average minimum element angle is 41.1 degrees.
A critical aspect of the correct implementation of the parallel algorithm is the synchronization necessary to avoid corrupted neighbor information. It is clear that two adjacent vertices cannot be smoothed simultaneously since the optimal position for the vertex in its local submesh depends critically on the positions of the incident vertices. This synchronization problem can be avoided if vertices that are not adjacent to each other are adjusted in parallel. Such a set of vertices is called an independent set. Once the vertices in the independent set are adjusted and incident vertices are notified of the new vertex location, another independent subset can be chosen for adjustment.
Previous: Mesh Generation
Next: Adaptive Mesh Refinement
Back: Unstructured Mesh Home Page