A parallel fast direct solver for block tridiagonal systems with separable matrices of arbitrary dimension

A parallel fast direct solution method for linear systems with separable block tridiagonal matrices is considered. Such systems appear, for example, when discretizing the Poisson equation in a rectangular domain using the five-point finite difference scheme or the piecewise linear finite elements on a triangulated, possibly nonuniform rectangular mesh. The method under consideration has the arithmetical complexity O(N log N), and it is closely related to the cyclic reduction method, but instead of using the matrix polynomial factorization, the so-called partial solution technique is employed. Hence, in this paper, the method is called the partial solution variant of the cyclic reduction method (PSCR method). The method is presented and analyzed in a general radix-q framework and, based on this analysis, the radix-4 variant is chosen for parallel implementation using the MPI standard. The generalization of the method to the case of arbitrary block dimension is described. The numerical experiments show the sequential efficiency and numerical stability of the PSCR method compared to the well-known BLKTRI implementation of the generalized cyclic reduction method. The good scalability properties of the parallel PSCR method are demonstrated in a distributed-memory Cray T3E-750 computer.