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. We present five novel algorithms for partitioning domains that utilize information from the underlying PDE. When a PDE has strong convection or anisotropic diffusion, 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 dependance. In our hundreds of experiments, the number of DD iterations required for convergence reduces by a factor between 0.25 and 0.75. In some cases, these methods improve the final finite element solution's accuracy also.