|
Vol: 4(4) No: 1 / March 1994 On the Divide and Conquer Algorithm for Solving Tridiagonal Systems Bogdan Dumitrescu Facultatea de Automatica si Calculatoare, Universitatea “Politehnica” Bucuresti, Spl. Independentei nr. 313, 77206, Bucuresti, Romania, e-mail: bogdan@indinf.pub.ro Keywords: tridiagonal linear systems Abstract Similar version of the divide and conquer algorithm and Wang’s partition method for solving tridiagonal linear systems are presented in the paper. A generalization of this version is derived in the sequel, on a parallel architecture, with a block row mapping of the system matrix on the processors. Using gaussian elimination, a reduced tridiagonal system of small dimension is obtained; the generalization consists in the use of any two equations of a processor in order to eliminate most of nondiagonal elements. References [1] R.W. Hockney A fast direct solution of Poisson’s equation using Fourier analysis. J. ACM, 12:95-113, 1965. [2] H. H. Wang. A parallel method for tridiagonal equations. ACM Trans. Math. Software, 7(2):170-183, 1981. [3] S. Lennart Johnsson. Solving Tridiagonal Systemson EnsembleArhitectures. SIAM J. Sci. Stat. Comput., 8:354-392, 1987. [4] B. Dumitrescu. Improvements for Wang partition method on MIMD arhitectures. In 9th Internat Conf. on Control Systems and Computer Science, Bucharest, pages 449-452,1993. [5] X. H. Sun H. Zhang and L. M. Ni. Efficient Tridiagonal Solvers on Multicomputers. IEEE Trans. Comput., 41(3):286-296,1992. [6] S. M. Muller A Method to Parallelize Tridiagonal Solvers. In 5th Distributed Memory Computing Conference, pages 340-345, 1990. [7] S. Bondeli Divide and Conquer: a new Parallel Algorithm for the Solution of a Tridiagonal Liniar Systems of Equations. In Lecture Notes in Computer Science 457, CONPAR 90, pages 108-119. Springer-Verlag, 1990. [8] C. T. Ho and S. Lennart Johnsson Optimizing Tridiagonal Solvers for Alternat-ing Direction Methods on Boolean Cube Multiprocessors. SIAM J. Sci. Stat. Comput., 11(3):563-592, 1990. [9] B. Dumitrescu Elementary tridiagonal system solvers on ring and hypercube. In 9th Internat Conf. on Control Systems and Computer Science, Bucharest, pages 453-457, 1993. |