Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society since 1960 (published as Mathematical Tables and other Aids to Computation 1943-1959), Mathematics of Computation is devoted to research articles of the highest quality in computational mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.78.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

A parallel algorithm for solving general tridiagonal equations
HTML articles powered by AMS MathViewer

by Paul N. Swarztrauber PDF
Math. Comp. 33 (1979), 185-199 Request permission

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. $O(n)$ storage is required for n equations and $O(\log n)$ operations are required on a parallel computer with n processors. $O(n)$ operations are required on a sequential computer. Experimental results are presented from both the CDC 7600 and CRAY-1 computers.
References
    O. BUNEMAN, A Compact Non-Iterative Poisson Solver, Rep. 294, Stanford Univ. Institute for Plasma Research, Stanford, Calif., 1969.
  • 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 287717, DOI 10.1137/0707049
    • 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., Carnegie-Mellon Univ., Pittsburgh, Pa., 1974.
  • Don Heller, A determinant theorem with applications to parallel algorithms, SIAM J. Numer. Anal. 11 (1974), 559–568. MR 348993, DOI 10.1137/0711048
  • R. W. Hockney, A fast direct solution of Poisson’s equation using Fourier analysis, J. Assoc. Comput. Mach. 12 (1965), 95–113. MR 213048, DOI 10.1145/321250.321259
    • 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. 136-211. P. M. KOGGE, Parallel Algorithms for the Efficient Solution of Recurrence Problems, Rep. 43, Digital Systems Laboratory, Stanford Univ., Stanford, Calif., 1972.
  • Jules J. Lambiotte Jr. and Robert G. Voigt, The solution of tridiagonal linear systems on the CDC STAR-100 computer, ACM Trans. Math. Software 1 (1975), no. 4, 308–329. MR 388843, DOI 10.1145/355656.355658
    • C. B. MOLER, "Cramer’s rule on 2-by-2 systems," ACM SIGNUM Newsletter, v. 9, 1974, pp. 13-14.
  • 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 334473, DOI 10.1145/321738.321741
  • Harold S. Stone, Parallel tridiagonal equation solvers, ACM Trans. Math. Software 1 (1975), no. 4, 289–307. MR 388842, DOI 10.1145/355656.355657
  • Paul N. Swarztrauber, A direct method for the discrete solution of separable elliptic equations, SIAM J. Numer. Anal. 11 (1974), 1136–1150. MR 368399, DOI 10.1137/0711086
  • J. F. Traub, Iterative solution of tridiagonal systems on parallel or vector computers, Complexity of sequential and parallel numerical algorithms (Proc. Sympos., Carnegie-Mellon Univ., Pittsburgh, Pa., 1973) Academic Press, New York, 1973, pp. 49–82. MR 0371146
Similar Articles
  • Retrieve articles in Mathematics of Computation with MSC: 65F05, 68C25
  • Retrieve articles in all journals with MSC: 65F05, 68C25
Additional Information
  • © Copyright 1979 American Mathematical Society
  • Journal: Math. Comp. 33 (1979), 185-199
  • MSC: Primary 65F05; Secondary 68C25
  • DOI: https://doi.org/10.1090/S0025-5718-1979-0514818-5
  • MathSciNet review: 514818