Refinement Tree Based Partitioning for Adaptive Grids.
William F. Mitchell · 1995
We present a new partitioning algorithm for grids obtained by adaptive refinement. The method uses the adaptive refinement tree to obtain information unavailable to other partitioning methods which use only the final grid and/or some geometric data. The algorithm requires (typically) O(log(N )) operations after an O(N ) preprocessing step. The method is guaranteed to produce perfectly balanced connected partitions. Numerical examples indicate that the partitions have only about 10% more crossings than methods that require many times the execution time, and unlike other methods, there is reason to expect similarity of the partitions of nested grids. 1 Introduction The numerical solution of partial differential equations (PDEs) is often the most computationally intensive part of solving mathematical models of physical phenomena. For this reason, much research has been performed to find faster methods to solve PDEs at higher resolution. A recent development involves the combination of so...