A parallel strategy for solving multidimensional tridiagonal equations is investigated in this paper. We present in detail an improved version of single parallel partition (SPP) algorithm in conjunction with message vectorization, which aggregates several communication messages into one to reduce the communication cost. We show the resulting block SPP can achieve good speedup for a wide range of message vector length (MVL), especially when the number of grid points in the divided direction is large. Instead of only using the largest possible MVL, we adopt numerical tests and modeling analysis to determine an optimal MVL so that significant improvement in speedup can be obtained.
EdisonT. W. and ErlebacherG., Implementation of a fully-balanced periodic tridiagonal solver on a parallel distributed memory architecture, Concurrency-pract EX 7, 1995, 4, 273–302.
2.
ZhangL. B., On pipelined computation of a set of recurrences on distributed memory systems, Journal on Numerical Methods and Computer Applications, 1999, 3, 184–191.
3.
BalasundaramV.FoxG.KennedyK. and KremerU., An Interactive Environment for Data Partitioning and Distribution, in: WalkerD.W. and StoutQ.F. ed., Architectures, Software Tools and Other General Issues (Vol. 2): Proceedings of the 5th Distributed Memory Computing Conference, ACM Press, New York, 1990, 1160–1170.
4.
HallM. W.HiranandaniS.KennedyK. and TsengC. W., Interprocedural compilation of fortran d for mimd distributed-memory machines, in: WernerR., ed., Conference on High Performance Networking and Computing: Proceedings of the 1992 ACM/IEEE conference on Supercomputing, IEEE Computer Society Press, Los Alamitos, CA, USA, 1992, 522–534.
5.
HockneyR. W., A fast direct solution of Poisson's equation using fourier analysis, Appendix Golub, G. H., Journal of the Association for Computing Machinery, 1965, 12, 95–113.
6.
HockneyR. W.StoneH.S., An effcient parallel algorithm for the solution of a tridiagonal linear system of equations, Journal of the Association for Computing Machinery, 1973, 20, 27–38.
7.
WakataniA., A parallel scheme for solving a tridiagonal matrix with prepropagation, Lecture Notes in Computer Science, 2003, 2840, 222–226.
8.
WangC. R.WangZ. H. and YangX. H., Computational Fluid Dynamics and Parallel Algorithms, National University of Defence Technology Press, Changsha, CHINA, 2000.
9.
WangH. H., A parallel method for tridiagonal equations, ACM Transactions on Mathematical Software, 1981, 7, 170–183.
10.
WakataniA., A parallel and scalable algorithm for ADI method with pre-propagation and message vectorization, Parallel Computing, 2004, 30, 1345–1359.
11.
YinZ.YuanL. and TangT., A new parallel strategy for two-dimensional incompressible flow simulations using pseudo-spectral methods, Journal of Computational Physics, 2005, 210, 325–341.
12.
YuanL., Comparison of implicit multigrid schemes for three-dimensional incompressible flows, Journal of Computational Physics, 2002, 177, 134–155.
13.
WimmerM., Experiments on a viscous fluid flow between concentric rotating spheres, Journal of Fluid Mechanics, 1976, 78, 317–335.
