Paper Info
Title
A New Block Parallel SOR Method and Its Analysis
Abstract
As the development of the PSOR method (a point parallel SOR method by mesh domain partitioning proposed in [SIAM J. Sci. Comput., 20 (1999), pp. 2261-2281], this paper introduces a new mesh domain partition and ordering (the multitype partition and ordering), and proposes a new block parallel SOR (BPSOR) method for numerically solving 2-dimensional (2D) or three-dimensional (3D) elliptic boundary problems. A general mathematical analysis shows that the BPSOR method can have the same asymptotic convergence rate as the corresponding sequential block SOR method if the coefficient matrix of the block linear system is "consistently ordered." It also shows that the original sequential ordering can be maintained in the parallel implementation of the BPSOR method so that the BPSOR method can be effectively applied to solve complex elliptic boundary problems. Furthermore, three particular multitype orderings are proposed based on strip and block mesh partitions, which lead to three effective BPSOR methods for solving the five-point like linear systems (in two dimensions) and the seven-point like linear systems (in three dimensions). In addition, it is shown that the PSOR method can be generated from BPSOR if each block equation is solved approximately by only one point SOR iteration. Thus, the PSOR method is well defined without involving any interprocessor data communication operations, and extended to solving three-dimensional (3D) problems. Finally, numerical results are presented which confirm the theoretical results and show that BPSOR has a good parallel performance on a parallel MIMD computer.
Year
DOI
Venue
2006
10.1137/040604777
SIAM J. Scientific Computing
Keywords
Field
DocType
bpsor method,psor,psor method,sor method,good parallel performance,block mesh partition,parallel computing,parallel sor method,block equation,block linear system,corresponding sequential block sor,domain decomposition,block sor,linear system,effective bpsor method,new block,mathematical analysis,three dimensions,2 dimensional,parallel computer,convergence rate,three dimensional,two dimensions
Direct method,Coefficient matrix,Linear system,Algorithm,Rate of convergence,Numerical analysis,Block matrix,Mathematics,Domain decomposition methods,Numerical linear algebra
Journal
Volume
Issue
ISSN
27
5
1064-8275
Citations 
PageRank 
References 
14
0.93
7
Authors
1
Name
Order
Citations
PageRank
Dexuan Xie16710.92