Dafna Talmor

Well-Spaced Points for Numerical Methods Degree Type: Ph.D. in Computer Science
Advisor(s): Gary Miller
Graduated: August 1997

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 M₀ 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 standard 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.