| | This Article | |
| |
| |
| | Share | |
| |
| |
| | Bibliographic References | |
| |
| |
| | Add to: | |
| |
 Digg
 Furl
 Spurl
 Blink
 Simpy
 Google
 Del.icio.us
 Y!MyWeb
| |
| | Search | |
| |
| |
| | |
Parallel Minimal Norm Method for Tridiagonal Linear Systems
July 1995 (vol. 44 no. 7)
pp. 942-946
Abstract—Based on the parallel minimal norm method an algorithm is derived to solve tridiagonal linear systems with a high degree of parallelism. No conditions need to be posed with respect to the system. Experiments indicate that the numerical stability of the algorithm is similar to Gaussian elimination with partial pivoting.
[1] 942 A.V. Aho,J.E. Hopcroft,, and J.D. Ullman., The Design and Analysis of Computer Algorithms. Addison-Wesley, 1974, pp. 60-67.[2] S. Bondeli,“Divide and conquer: A parallel algorithm for the solution of a tridiagonal linear system of equations,” Parallel Computing, vol. 17, no. 4-5, pp. 419-434, July 1991.[3] E. Dekker and L. Dekker,“Parallel minimal norm method for direct solving of linear algebraic equations,” J. Systems Analysis and Modeling Simulation, vol. 6, no. 9, pp. 643-657, Sept. 1989.[4] Ö. ${\rm E}\!\!\buildrel \smile \over {\rm g}\!\!{\rm ecio}\!\!\buildrel \smile \over {\rm g}\!\!{\rm lu}$,C.K. Koc,, and A.J. Laub,“A recursive doubling algorithm for solution of tridiagonal systems on hypercube multiprocessors,” J. Comp. Appl. Math., vol. 27, pp. 95-108, 1989.[5] G.H. Golub and C.F. Van Loan., Matrix Computations.Baltimore: Johns Hopkins Univ. Press, 1983, pp. 92-98.[6] Intel Corporation. Paragon XP/S Product Overview.Beaverton, Ore.: Intel Corporation, 1991.[7] C. Kamath and A. Sameh,“A projection method for solving nonsymmetric linear systems on multiprocessors,” Parallel Computing, vol. 9, no. 3, pp. 291-312, Feb. 1989.[8] J.J. Lambiotte and R.G. Voigt,“The solution of tridiagonal linear systems on the CDC STAR-100 computer,” ACM Trans. Math. Soft., vol. 1, no. 4, pp. 308-329, Dec. 1975.[9] J.M. Ortega and R.G. Voigt,“Solution of partial differential equations on vector and parallel computers,” SIAM Rev., vol. 27, no. 2, pp. 149-240, June 1985.[10] H.S. Stone, “An Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of Equations,” J. ACM, vol. 20, pp. 27, 1973.[11] X.-H. Sun, H. Zhang, and L. Ni, Efficient Tridiagonal Solvers on Multicomputers IEEE Trans. Computers, vol. 41, no. 3, pp. 286-296, 1992.[12] Thinking Machines Corporation. The Connection Machine CM-5 Technical Summary.Cambridge, Mass.: Thinking Machines Corporation, 1992.[13] H.H. Wang,“A parallel method for tridiagonal equations,” ACM Trans. Math. Soft., vol. 7, no. 2, pp. 170-183, June 1981.
Index Terms:
Parallel algorithms, parallel minimal norm method, tridiagonal linear systems, row-oriented orthogonalization, structural orthogonality.
Citation:
L. Dekker, E. Dekker, "Parallel Minimal Norm Method for Tridiagonal Linear Systems," IEEE Transactions on Computers, vol. 44, no. 7, pp. 942-946, July 1995, doi:10.1109/12.392854
