A parallel algorithm for solving general tridiagonal equations
Author:
Paul N. Swarztrauber
Journal:
Math. Comp. 33 (1979), 185199
MSC:
Primary 65F05; Secondary 68C25
MathSciNet review:
514818
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: A parallel algorithm for the solution of the general tridiagonal system is presented. The method is based on an efficient implementation of Cramer's rule, in which the only divisions are by the determinant of the matrix. Therefore, the algorithm is defined without pivoting for any nonsingular system. storage is required for n equations and operations are required on a parallel computer with n processors. operations are required on a sequential computer. Experimental results are presented from both the CDC 7600 and CRAY1 computers.
 [1]
O. BUNEMAN, A Compact NonIterative Poisson Solver, Rep. 294, Stanford Univ. Institute for Plasma Research, Stanford, Calif., 1969.
 [2]
B.
L. Buzbee, G.
H. Golub, and C.
W. Nielson, On direct methods for solving Poisson’s
equations, SIAM J. Numer. Anal. 7 (1970),
627–656. MR 0287717
(44 #4920)
 [3]
D. E. HELLER, D. K. STEVENSON & J. F. TRAUB, Accelerated Iterative Methods for the Solution of Tridiagonal Systems on Parallel Computers, Dept. Computer Sci. Rep., CarnegieMellon Univ., Pittsburgh, Pa., 1974.
 [4]
Don
Heller, A determinant theorem with applications to parallel
algorithms, SIAM J. Numer. Anal. 11 (1974),
559–568. MR 0348993
(50 #1487)
 [5]
R.
W. Hockney, A fast direct solution of Poisson’s equation
using Fourier analysis, J. Assoc. Comput. Mach. 12
(1965), 95–113. MR 0213048
(35 #3913)
 [6]
R. W. HOCKNEY, "The potential calculation and some applications," Methods of Computational Physics, B. Adler, S. Fernback and M. Rotenberg (Eds.), Academic Press, New York, 1969, pp. 136211.
 [7]
P. M. KOGGE, Parallel Algorithms for the Efficient Solution of Recurrence Problems, Rep. 43, Digital Systems Laboratory, Stanford Univ., Stanford, Calif., 1972.
 [8]
Jules
J. Lambiotte Jr. and Robert
G. Voigt, The solution of tridiagonal linear systems on the CDC
STAR100 computer, ACM Trans. Math. Software 1
(1975), no. 4, 308–329. MR 0388843
(52 #9677)
 [9]
C. B. MOLER, "Cramer's rule on 2by2 systems," ACM SIGNUM Newsletter, v. 9, 1974, pp. 1314.
 [10]
Harold
S. Stone, An efficient parallel algorithm for the solution of a
tridiagonal linear system of equations, J.Assoc. Comput. Mach.
20 (1973), 27–38. MR 0334473
(48 #12792)
 [11]
Harold
S. Stone, Parallel tridiagonal equation solvers, ACM Trans.
Math. Software 1 (1975), no. 4, 289–307. MR 0388842
(52 #9676)
 [12]
Paul
N. Swarztrauber, A direct method for the discrete solution of
separable elliptic equations, SIAM J. Numer. Anal. 11
(1974), 1136–1150. MR 0368399
(51 #4640)
 [13]
J.
F. Traub, Iterative solution of tridiagonal systems on parallel or
vector computers, Complexity of sequential and parallel numerical
algorithms (Proc. Sympos., CarnegieMellon Univ., Pittsburgh, Pa., 1973)
Academic Press, New York, 1973, pp. 49–82. MR 0371146
(51 #7367)
 [1]
 O. BUNEMAN, A Compact NonIterative Poisson Solver, Rep. 294, Stanford Univ. Institute for Plasma Research, Stanford, Calif., 1969.
 [2]
 B. L. BUZBEE, G. H. GOLUB & C. W. NIELSON, "On direct methods for solving Poisson's equations," SIAM J. Numer. Anal., v. 7, 1970, pp. 627656. MR 0287717 (44:4920)
 [3]
 D. E. HELLER, D. K. STEVENSON & J. F. TRAUB, Accelerated Iterative Methods for the Solution of Tridiagonal Systems on Parallel Computers, Dept. Computer Sci. Rep., CarnegieMellon Univ., Pittsburgh, Pa., 1974.
 [4]
 D. E. HELLER, "A determinant theorem with applications to parallel algorithms," SIAM J. Numer. Anal., v. 11, 1974, pp. 559568. MR 0348993 (50:1487)
 [5]
 R. W. HOCKNEY, "A fast direct solution of Poisson's equation using Fourier analysis," J. Assoc. Comput. Mach., v. 8, 1965, pp. 95113. MR 0213048 (35:3913)
 [6]
 R. W. HOCKNEY, "The potential calculation and some applications," Methods of Computational Physics, B. Adler, S. Fernback and M. Rotenberg (Eds.), Academic Press, New York, 1969, pp. 136211.
 [7]
 P. M. KOGGE, Parallel Algorithms for the Efficient Solution of Recurrence Problems, Rep. 43, Digital Systems Laboratory, Stanford Univ., Stanford, Calif., 1972.
 [8]
 J. R. LAMBIOTTE, JR. & R. G. VOIGT, "The solution of tridiagonal linear systems on the CDC STAR100 computer," ACM Trans. Math. Software., v. 1, 1975, pp. 308329. MR 0388843 (52:9677)
 [9]
 C. B. MOLER, "Cramer's rule on 2by2 systems," ACM SIGNUM Newsletter, v. 9, 1974, pp. 1314.
 [10]
 H. S. STONE, "An efficient parallel algorithm for the solution of a tridiagonal linear system of equations," J. Assoc. Comput. Mach., v. 20, 1973, pp. 2738. MR 0334473 (48:12792)
 [11]
 H. S. STONE, "Parallel tridiagonal equation solvers," ACM Trans. Math. Software., v. 1, 1975, pp. 289307. MR 0388842 (52:9676)
 [12]
 P. N. SWARZTRAUBER, "A direct method for the discrete solution of separable elliptic equations," SIAM J. Numer. Anal., v. 11, 1974, pp. 11361150. MR 0368399 (51:4640)
 [13]
 J. F. TRAUB, "Iterative solution of tridiagonal systems on parallel or vector computers," Complexity of Sequential and Parallel Numerical Algorithms, J. F. Traub (Ed.), Academic Press, New York, 1973, pp. 4982. MR 0371146 (51:7367)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65F05,
68C25
Retrieve articles in all journals
with MSC:
65F05,
68C25
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718197905148185
PII:
S 00255718(1979)05148185
Keywords:
Tridiagonal matrices,
parallel algorithms,
linear equations
Article copyright:
© Copyright 1979
American Mathematical Society
