A BSP recursive divide and conquer algorithm to solve a tridiagonal linear system. (English) Zbl 1060.65032

Summary: We discuss a recursive divide and conquer method to solve a tridiagonal system of linear equations. We propose two divide and conquer algorithms using different communication schemes. The first one uses a fan-in scheme to perform communication among processors, while the second one follows a rather different model, in which all the processors communicate all data to the main one. A theoretical study of the computational cost of both algorithms is developed computing theoretical times; firstly in an IBM SP2 computer with a high performance switch and Ethernet connection, and secondly in a CRAY T3D computer. We present experimental results for the IBM SP2 computer, for 2, 4, and 8 processors, comparing these results with the theoretical predicted times.


65F05 Direct numerical methods for linear systems and matrix inversion
65F50 Computational methods for sparse matrices
65Y20 Complexity and performance of numerical algorithms


Full Text: DOI


[1] Bondeli, S., Divide and conquer: a parallel algorithm for the solution of a tridiagonal linear system of equations, Parallel computing, 17, 419-434, (1991) · Zbl 0739.65016
[2] Climent, J.-J.; Tortosa, L.; Zamora, A., A BSP recursive divide and conquer algorithm to compute the inverse of a tridiagonal matrix, Journal of parallel and distributed computing, 59, 423-444, (1999) · Zbl 0958.68189
[3] Climent, J.-J.; Tortosa, L.; Zamora, A., A note on the recursive decoupling method for solving tridiagonal linear systems, Applied mathematics and computation, 140, 159-164, (2003) · Zbl 1027.65038
[4] Evans, D.J.; Barulli, M., BSP linear solvers for dense matrices, Parallel computing, 24, 777-795, (1998) · Zbl 0909.68013
[5] Gerbessiotis, A.V.; Valliant, L.G., Direct bulk-synchronous parallel algorithms, Journal of parallel and distributed computing, 22, 251-267, (1994)
[6] Hill, J.M.; McColl, B.; Stefanescu, D.C.; Goudreau, M.W.; Lang, K.; Rao, S.B.; Suel, T.; Tsantilas, T.; Bisseling, R.H., Bsplib: the BSP programming library, Parallel computing, 24, 1947-1980, (1998)
[7] Hockney, R., A fast direct solution of Poisson’s equation using Fourier analysis, Journal of the ACM, 12, 95-113, (1965) · Zbl 0139.10902
[8] Huang, Y.; McColl, W.F., A two-way BSP algorithm for tridiagonal systems, Future generation computer systems, 13, 337-347, (1998)
[9] McColl, W.F., BSP programming, (), 21-35
[10] McColl, W.F., Scalable computing, (), 46-61
[11] Mehrmann, V., Divide and conquer for block tridiagonal systems, Parallel computing, 19, 257-279, (1993) · Zbl 0765.65035
[12] Sameh, A.; Kuck, D., On stable parallel linear system solvers, Journal of the ACM, 25, 81-91, (1978) · Zbl 0364.68051
[13] Spaletta, G.; Evans, D.J., The parallel recursive decoupling algorithm for solving tridiagonal linear systems, Parallel computing, 19, 563-576, (1993) · Zbl 0783.65021
[14] Stone, H., An efficient parallel algorithm for the solution of a tridiagonal linear system of equations, Journal of the ACM, 20, 27-38, (1973) · Zbl 0269.65018
[15] L. Tortosa, Algoritmos divide y vencerás para la resolución de sistemas lineales tridiagonales en un computador BSP (in Spanish), Ph.D. Thesis, Departament de Ciència de la Computació i Intel·ligència Artificial, Universitat d’Alacant, 2000
[16] Valiant, L.G., A bridging model for parallel computation, Communications of the ACM, 33, 103-111, (1990)
[17] Wang, H.H., A parallel method for tridiagonal equations, ACM transactions on mathematical software, 7, 170-183, (1981) · Zbl 0473.65010
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.