Well-Spaced Points for Numerical Methods
Abstract
A numerical method for the solution of a partial differential equation (PDE) requires the following steps: (1) discretizing the domain (mesh generation); (2) using an approximation method and the mesh to transform the problem into a linear system; (3) solving the linear system. The approximation error and convergence of the numerical method depend on the geometric quality of the mesh, which in turn depends on the size and shape of its elements. For example, the shape quality of a triangular mesh is measured by its element's aspect ratio. 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 M1,...,Mk such that Mi 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 standard aspect-ratio condition in that it allows slivers.
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1997
- Accession Number
- ADA333297
Entities
People
- Dafna Talmor
Organizations
- Carnegie Mellon University