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

A parallel fast direct solution method for linear systems with separable bl ock tridiagonal matrices is considered. Such systems appear, for example, w hen discretizing the Poisson equation in a rectangular domain using the fiv e-point finite difference scheme or the piecewise linear finite elements on a triangulated, possibly nonuniform rectangular mesh. The method under con sideration has the arithmetical complexity O(N log N), and it is closely re lated to the cyclic reduction method, but instead of using the matrix polyn omial 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 anal yzed 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 d escribed. The numerical experiments show the sequential efficiency and nume rical stability of the PSCR method compared to the well-known BLKTRI implem entation of the generalized cyclic reduction method. The good scalability p roperties of the parallel PSCR method are demonstrated in a distributed-mem ory Cray T3E-750 computer.