We present a fast direct solver, ACR, for structured sparse linear systems that arise from the discretization of 2D elliptic operators. The solver approximates every block using an H-Matrix, resulting in a log-linear arithmetic complexity of O(N log~2 N) with memory requirements of O(N log N). Robustness and applicability are demonstrated on model scalar problems and contrasted with established solvers based on the H-LU factorization and algebraic multigrid. Multigrid maintains superiority in scalar problems with sufficient defi-niteness and symmetry, whereas hierarchical matrix-based replacements of direct methods tackle some problems where these properties are lacking. Although being of the same asymptotic complexity as H-LU, ACR has fundamentally different algorithmic roots which produce a novel alternative for a relevant class of problems with competitive performance, and concurrency that grows with the problem size. In Chavez et al. (2016) we expand on the consideration of cyclic reduction as a fast direct solver for 3D elliptic operators.
展开▼
