An Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of Equations

ABSTRACT

Tridiagonal linear systems of equations can be solved on conventional serial machines in a time proportional to N, where N is the number of equations. The conventional algorithms do not lend themselves directly to parallel computation on computers of the ILLIAC IV class, in the sense that they appear to be inherently serial. An efficient parallel algorithm is presented in which computation time grows as log2 N. The algorithm is based on recursive doubling solutions of linear recurrence relations, and can be used to solve recurrence relations of all orders.

REFERENCES

• 1: BUNEMAN, OSCAR A compact non-iterat~ve Poisson solver. Rep. 294, Inst. for Plasma Res., Stanford U., Stanford, Calif., 1969.
• 2: BUZBEE, B. L, GOLUB, G. H, AND NIELSON, C.W. On direct methods for solving Poisson's equations. SIAM J. Numer. Anal 7, 4 (Dec. 1970), 627-656.
• 3: EULER, LEONHARD. Introduct~o ~n Analys~n infin~torum, Lausanne, 1748, Sec. 359.
• 4: FORSYTHE, G. E., AND MOLEa, C. B. Computer Solution of Linear Algebraic Systems. Prentice-Hall, Englewood Cliffs, N. J., 1967.
• 5: GAUTSCm, WALTER. Computational aspects of three-term recurrence relations, SIAM Rev. 9, 1, (Jan. 1967), 24-82.
• 6: ISAACSON, E., AND KELLER, H.B. Analysis of Numerwal Methods. Wiley, New York, 1966.
• 7: KNUTH, D. E. Mathematical analysm of algorithms. Rep. Stan-CS-71-206, Computer Sci. Dep., Stanford U., Stanford, Calif., Mar. 1971.
• 8: PERRON, O. D~e Lehre yon den Kettenbruchen. Leipzig, 1913.
• 9: SYLVEST~R, J.J. Philosophical Magazine 6, (1853), 297-299.
• 10: WALL, H.S. Analytic Theory of Continued Fractions. Van Nostrand, New York, 1948.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

General Terms:
Algorithms, Theory, Verification