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

Citation
T. Rossi et J. Toivanen, A parallel fast direct solver for block tridiagonal systems with separablematrices of arbitrary dimension, SIAM J SC C, 20(5), 1999, pp. 1778-1796
Citations number
32
Categorie Soggetti
Mathematics
Journal title
SIAM JOURNAL ON SCIENTIFIC COMPUTING
ISSN journal
10648275 → ACNP
Volume
20
Issue
5
Year of publication
1999
Pages
1778 - 1796
Database
ISI
SICI code
1064-8275(19990521)20:5<1778:APFDSF>2.0.ZU;2-7
Abstract
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.