A parallel fast direct solver based on the Divide & Conquer method is considered for linear systems with separable block tridiagonal matrices. Such systems are obtained, for example, by discretizing the two--dimensional Poisson equation posed on rectangula
A Parallel Fast Direct Solver for the Discrete Solution of Separable Elliptic Equations Tuomo Rossi Jari Toivanen
Abstract A parallel fast direct solver based on the Divide& Conquer method is considered for linear systems with separable block tridiagonal matrices. Such systems are obtained, for example, by discretizing the two{dimensional Poisson equation posed on rectangular domains with the continuous piecewise linear nite elements on nonuniform triangulated rectangular meshes. The Divide& Conquer method has the arithmetical complexity O(N log N ), and it is closely related to the cyclic reduction, but instead of using the matrix polynomial factorization, the so{called partial solution technique is employed. The parallel implementation using the MPI standard is described and a good parallel scalability of the proposed method is demonstrated on an IBM SP2 parallel computer. Also, the sequential performance is compared with the well{known BLKTRI{implementation of the generalized cyclic reduction method using a single processor of IBM SP2.
The fast direct solution of linear elliptic boundary value problems has received continuous attention since 1965, when R. W. Hockney published the paper 7]. For further development of fast direct solvers, see, for example, 15], and references therein. Parallelization of such methods has also gained a lot of interest. In 17], a parallel version of the fast Fourier transform solver is considered and analyzed. The parallel FACR{method is studied in the framework of shared memory 3] and vector computers 8]. The parallel implementation of the cyclic reduction algorithm using the partial fraction expansions of rational matrix functions was introduced by R. A. Sweet in 1986, and further discussed in 4, 18]. In this paper, we are concerned with a relatively new O(N log N ){method, which was originally introduced in 19] and further considered in 9]. In 11], this method was named Divide& Conquer method (DC{method), and a general base q variant (q 2) was given in the case of separable block band matrices. In 12], the stability of the the DC{method and the close relation to the cyclic odd{even reduction is analyzed. The generality of the DC{method is mainly based on the use of the partial solution techniques 2, 10]. Basing on the estimates given in 13], we choose the base four variant for parallelization in the case of block tridiagonal matrices arising, for example, from the second{order separable elliptic problems. We describe the parallel implementation of the DC{method on a distributed memory parallel computer using the MPI message passing standard 14]. The implementation of the base two variant in an array processor has been described in 1]. Laboratory of Scienti c Computing, Department of Mathematics, University of Jyvaskyla, P.O. Box 35, FIN-40351 Jyvaskyla, Finland. (Tuomo.Rossi@math.jyu.fi, Jari.Toivanen@math.jyu.fi).
1 Introduction
A PARALLEL FAST DIRECT SOLVER WITH APPLICATIONS Raino A. E. Makinen Tuomo ... E cient fortran subprograms for the solution of separable elliptic partial ...
Toivanen: A parallel fast direct solver for block tridiagonal systems with separable matrices of arbitrary dimension, SIAM J. Sci. Comput. 20(1999), pp....
In addition, solver is parallel in nature. It ...separable and method domain direct elliptic works ...solution, size N2 and size h2 for the 2 ...
热门文档