Domain Partitioning Methods for Elliptic Partial Differential Equations

Numerically solving elliptic partial differential equations for a large number of degrees of freedom requires the parallel use of many computer processors. This in turn requires algorithms to partition domains into subdomains in order to distribute the work. In this dissertation, we present five novel algorithms for partitioning domains that utilize information from the underlying PDE. When a PDE has strong convection or anisotropic diffusion, directional dependence exists and a partition that favors this direction is desirable. Our schemes fall into two classes; one class creates rectangular shaped subdomains aligned in this direction and one class creates subdomains that increase in size as you move in this direction. These schemes are mathematically described and analyzed in detail. Then they are tested on a variety of experiments which include solving the convection-diffusion equation for 1/4 billion unknowns on 512 processors using over 1 teraflop of computing power. Theory and experiments demonstrate that these schemes improve the domain decomposition convergence rate when the underlying PDE has directional dependence. In our hundreds of experiments, the number of DD iterations required for convergence reduces by a factor between 0.25 and 0.75. And these methods maintain or improve the final finite element solution's accuracy als