  This paper studies a low-communication algorithm for solving elliptic partial
differential equations (PDE's) on high-performance machines, the nested
iteration with range decomposition algorithm (NIRD). Previous work has shown
that NIRD converges to a high level of accuracy within a small, fixed number of
iterations (usually one or two) when applied to simple elliptic problems. This
paper makes some improvements to the NIRD algorithm (including the addition of
adaptivity during preprocessing, wider choice of partitioning functions, and
modified error measurement) that enhance the method's accuracy and scalability,
especially on more difficult problems. In addition, an updated convergence
proof is presented based on heuristic assumptions that are supported by
numerical evidence. Furthermore, a new performance model is developed that
shows increased performance benefits for NIRD when problems are more expensive
to solve using traditional methods. Finally, extensive testing on a variety of
elliptic problems provides additional insight into the behavior of NIRD and
additional evidence that NIRD achieves excellent convergence on a wide class of
elliptic PDE's and, as such, should be a very competitive method for solving
PDE's on large parallel computers.
