CMU-CS-97-164 Computer Science Department School of Computer Science, Carnegie Mellon University
Well-Spaced Points for Numerical Methods Dafna Talmor August 1997 Ph.D. Thesis
CMU-CS-97-164.ps
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 M_{0} is a sequence of good aspect-ratio meshes M_{i}, ..., M _{k} such that M_{i} is an approximation of M_{i - 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. 177 pages
| |
Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |