A Grid-Based Subtree-Subcube Assignment Strategy for Solving Partial Differential Equations on Hypercubes

The authors propose a grid-based subtree-subcube assignment strategy for solving PDE problems on hypercubes. A complexity analysis of the communication is given for the proposed approach and the standard subtree-subcube assignment when applied to a variant of nested dissection indexing and a nonsymmetric sparse solver. The new assignment reduces communication cost using p processors by a factor of $O(\log p)$ in message startups and a factor of about two in traffic volume. Using a modified nested dissection indexing, the total effect on message startups is a reduction by a factor of $O(\log N)$ compared to previous approaches, where N is the number of unknowns. This grid-based assignment strategy achieves the optimal order in both traffic volume and startups; it provides good load balancing and as much parallelism as is inherent in the underlying algorithm. Some experimental results are presented which confirm the increased communication efficiency.