Computer Science Department
School of Computer Science, Carnegie Mellon University
Well-Spaced Points for Numerical Methods
In this work we shift the focus to the geometric properties of the nodes, rather than the elements, of well shaped meshes. We introduce the concept of well-spaced points and their spacing functions, and show that these enable the development of simple and efficient algorithms for the different stages of the numerical solution of PDEs.
We first apply well-spaced point sets and their accompanying technology to mesh coarsening, a crucial step in the multigrid solution of a PDE. A good aspect-ratio coarsening sequence of an unstructured mesh M0 is a sequence of good aspect-ratio meshes Mi, ..., M k such that Mi is an approximation of Mi - 1 containing fewer nodes and elements. We present a new approach to coarsening that guarantees the sequence is also of optimal size and width up to a constant factor --- the first coarsening method that provides these guarantees. We also present experimental results, based on an implementation of our approach, that substantiate the theoretical claims.
In three dimensions, we apply well-spaced points to mesh generation. We introduce a new aspect-ratio condition, the radius-edge ratio, which corresponds to well-spaced points. Radius-edge ratio is weaker than the s tandard aspect-ratio condition in that it allows slivers. Nonetheless, we show that a Delaunay mesh of bounded radius-edge ratio has geometric structure properties that are reminiscent of a bounded standard aspect-ratio mesh: the mesh is a density graph and its Voronoi cells are well-shaped. We finally show how to construct such meshes to conform to an input domain.