| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
A Parallel Two-Level Hybrid Method for Tridiagonal Systems and Its Application to Fast Poisson Solvers
February 2004 (vol. 15 no. 2)
pp. 97-106
Abstract—A new method, namely, the Parallel Two-Level Hybrid (PTH) method, is developed to solve tridiagonal systems on parallel computers. PTH has two levels of parallelism. The first level is based on algorithms developed from the Sherman-Morrison modification formula, and the second level can choose different parallel tridiagonal solvers for different applications. By choosing different outer and inner solvers and by controlling its two-level partition, PTH can deliver better performance for different applications on different machine ensembles and problem sizes. In an extreme case, the two levels of parallelism can be merged into one, and PTH can be the best algorithm otherwise available. Theoretical analyses and numerical experiments indicate that PTH is significantly better than existing methods on massively parallel computers. For instance, using PTH in a fast Poisson solver results in a 2-folds speedup compared to a conventional parallel Poisson solver on a 512 nodes IBM machine. When only the tridiagonal solver is considered, PTH is over 10 times faster than the currently used implementation.
[1] 97 I. Duff, A. Erisman, and J. Reid, Direct Methods for Sparse Matrices. Clarendon Press, Oxford, 1986.[2] O. Egecioglu, D. Koc, and A. Laub, A Recursive Doubling Algorithm for Solution of Tridiagonal Systems on Hypercube Multiprocessors J. Computational and Applied Math., vol. 27, 1989.[3] T.M. Edison and G. Erlebacher, Implementation of a Fully-Balanced Periodic Tridiagonal Solver on a Parallel Distributed Memory Architecture Concurrency: Practics and Experience, 1995.[4] C. Ho and S. Johnsson, Optimizing Tridiagonal Solvers for Alternating Direction Methods on Boolean Cube Multiprocessors SIAM J. Scientific and Statistical Computing, vol. 11, no. 3, pp. 563-592, 1990.[5] R.W. Hockney, A Fast Direct Solution of Poisson's Equation Using Fourier Analysis J. ACM, vol. 12, pp. 95-113, 1965.[6] R.W. Hockney, Parallel Computers 2, Architecture, Programming and Algorithms. Adam Hilger, 1988.[7] IBM, Parallel Engineering and Scientific Subroutine Library for AIX, third ed. 1999, http:/www.rs6000.ibm.com.[8] D. Lawrie and A. Sameh, The Computation and Communication Complexity of a Parallel Banded System Solver ACM Trans. Mathmatic Software, vol. 10, no. 2, pp. 155-195, June 1984.[9] J. Ortega and R. Voigt, Solution of Partial Differential Equations on Vector and Parallel Computers SIAM Rev., pp. 149-240, 1985.[10] J. Sherman and W. Morrison, Adjustment of an Inverse Matrix Corresponding to Changes in the Elements of a Given Column or a Given Row of the Original Matrix Ann. Math Statistics, vol. 20, p. 618, 1949.[11] H. Stone, An Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of Equations J. ACM, vol. 20, no. 1, pp. 27-38, Jan. 1973.[12] X.-H. Sun, Application and Accuracy of the Parallel Diagonal Dominant Algorithm Parallel Computing, vol. 18, pp. 1241-1267, 1995.[13] X.-H. Sun and S. Moitra, Performance Comparison of a Set of Periodic and Nonperiodic Tridiagonal Solvers on SP2 and Paragon Parallel Computers Concurrency: Practice and Experience, vol. 9, no. 8, pp. 781-801, 1997.[14] X.-H. Sun and D. Rover, “Scalability of Parallel Algorithm-Machine Combinations,” IEEE Trans. Parallel and Distributed Systems, vol. 5, no. 6, pp. 599-613, June 1994.[15] X.-H. Sun, H. Zhang, and L. Ni, Efficient Tridiagonal Solvers on Multicomputers IEEE Trans. Computers, vol. 41, no. 3, pp. 286-296, 1992.[16] X.-H. Sun and J. Zhu, “Performance Considerations of Shared Virtual Memory Machines,” IEEE Trans. Parallel and Distributed Systems, vol. 6, no. 11, pp. 1,185-1,194, Nov. 1995.[17] A.J. Wallcraft and D.R. Moore, The NRL Layered Ocean Model Parallel Computing, vol. 23, pp. 2227-2242, 1997.[18] H. Wang, A Parallel Method for Tridiagonal Equations ACM Trans. Math Software, vol. 7, pp. 170-153, 1981.[19] P. Arbenz, A. Cleary, J. Dongarra, and M. Hegland, A Comparison of Parallel Solvers for Diagonally Dominant and General Narrow Banded Linear Systems Parallel and Distributed Computing Practices, vol. 2, pp. 385-400, 1999.
Index Terms:
Parallel processing, scalable computing, tridiagonal systems, Poisson solver.
Citation:
Xian-He Sun, Wu Zhang, "A Parallel Two-Level Hybrid Method for Tridiagonal Systems and Its Application to Fast Poisson Solvers," IEEE Transactions on Parallel and Distributed Systems, vol. 15, no. 2, pp. 97-106, Feb. 2004, doi:10.1109/TPDS.2004.1264794
