Optimal Good-Aspect-Ratio Coarsening for Unstructured Meshes

G. L. Miller, D. Talmor and S. H. Teng
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms , January, 1997, New Orleans, LA

410k compressed postscript of paper

1675k compressed postscript of talk slides

Abstract: A hierarchical gradient of an unstructured mesh M_0 is a sequence of meshes M_1,....,M_k such that |M_k| is smaller than a given threshold mesh size b . The gradient is well-conditioned if for each i in the range 1<=i<=k ,

M_i is well-shaped, namely, elements of M_i have a bounded aspect ratio; and
M_i is a coarsened approximation of M_{i-1}.

The gradient is node-nested if the set of the nodes of M_i is a subset of that of M_{i-1}.
The problem of constructing well-conditioned coarsening gradients is a key step for hierarchical and multi-level numerical calculations. In this paper, we give an algorithm for finding a well-conditioned hierarchical gradient of a two dimensional unstructured mesh. Our algorithm can be used to generate both node-nested and non-nested gradients. The gradient M_1,....,M_k we generate is optimal in the following sense: there exists a constant c such that for any other well-conditioned hierarchical gradient M'_1,......,M'_k, |M_i| < c |M'_i|, that is, the size of the mesh at each level is smaller up to a constant factor.

@inproceedings{MiTaTe97,
     Author="G.~L. Miller and D. Talmor and S.~H. Teng",
     Title="Optimal Good-Aspect-Ratio Coarsening for Unstructured Meshes",
     Booktitle="Proceedings of the Eighth Annual ACM-SIAM Symposium 
                on Discrete Algorithms",
     Year=1997,
     month=January}