Optimal coarsening of unstructured meshes

A bounded aspect-ratio coarsening sequence of an unstructured mesh M-0 is a sequence of meshes M-1,..., M-k, such that: M-i is a bounded aspect-ratio mesh, and M-l is an approximation of Mi-l that has fewer elements, where a mesh is called a bounded aspect-ratio mesh if all its elements are of bounded aspect-ratio. The sequence is node-nested if the set of the node s of M-i is a subset of that of Mi-l. The problem of constructing good qual ity coarsening sequences is a key step for hierarchical and multilevel nume rical calculations. In this paper, we give an algorithm for finding a bound ed aspect-ratio, node-nested, coarsening sequence that is of optimal size: that is, the number of meshes in the sequence, as well as the number of ele ments in each mesh, are within a constant factor of the smallest possible. (C) 1999 Academic Press.