Self-avoiding walks over adaptive unstructured grids
✍ Scribed by Heber, Gerd; Biswas, Rupak; Gao, Guang R.
- Publisher
- John Wiley and Sons
- Year
- 2000
- Tongue
- English
- Weight
- 467 KB
- Volume
- 12
- Category
- Article
- ISSN
- 1040-3108
No coin nor oath required. For personal study only.
✦ Synopsis
In this paper, we present self-avoiding walks as a novel technique to 'linearize' an unstructured mesh. Unlike space-filling curves which are based on a geometric embedding, our strategy is combinatorial since it uses the mesh connectivity only. We formulate a linear time-complexity algorithm for the construction of these self-avoiding walks over a triangular mesh. We also show how the concept can be easily modified for adaptive grids that are generated in a hierarchical manner based on a set of simple rules, and made amenable for efficient parallelization. We suggest a metric that might be used to evaluate the quality of such walks and present some sample results. The proposed locality-enhancing approach should be very useful in the runtime partitioning and load balancing of adaptive unstructured grids.