  We present Accelerated Cyclic Reduction (ACR), a distributed-memory fast
direct solver for rank-compressible block tridiagonal linear systems arising
from the discretization of elliptic operators, developed here for three
dimensions. Algorithmic synergies between Cyclic Reduction and hierarchical
matrix arithmetic operations result in a solver that has $O(k~N \log N~(\log N
+ k^2))$ arithmetic complexity and $O(k~N \log N)$ memory footprint, where $N$
is the number of degrees of freedom and $k$ is the rank of a typical
off-diagonal block, and which exhibits substantial concurrency. We provide a
baseline for performance and applicability by comparing with the multifrontal
method where hierarchical semi-separable matrices are used for compressing the
fronts, and with algebraic multigrid. Over a set of large-scale elliptic
systems with features of nonsymmetry and indefiniteness, the robustness of the
direct solvers extends beyond that of the multigrid solver, and relative to the
multifrontal approach ACR has lower or comparable execution time and memory
footprint. ACR exhibits good strong and weak scaling in a distributed context
and, as with any direct solver, is advantageous for problems that require the
solution of multiple right-hand sides.
