文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > A Parallel Fast Direct Solver for the Discrete Solution of Separable Elliptic Equations
侵权投诉

A Parallel Fast Direct Solver for the Discrete Solution of Separable Elliptic Equations

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

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email