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 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

@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}