Parallel algorithms for solution of tridiagonal systems on multicomputers

ABSTRACT

Three parallel algorithms, namely the parallel partition LU (PPT) algorithm, the parallel partition hybrid (PPH) algorithm, and the parallel diagonal dominant (PDD) algorithm are proposed for solving tridiagonal linear systems on multicomputers. These algorithms are based on the divide-and-conquer parallel computation model. The PPT and PPH algorithms support both pivoting and non-pivoting. The PPT algorithm is good when the number of processors is small; otherwise, the PPH algorithm is better. When the system is diagonal dominant, the PDD algorithm is highly parallel and provides an approximate solution which equals to the exact solution within machine accuracy. Both computation and communication complexities of the three algorithms are presented. All three methods proposed in this paper outperform other known parallel algorithms and have been implemented on a 64-node Ncube multicomputer. The analytic results matches closely with the results measured from the Ncube machine.

REFERENCES

• AtSe88: William C. Athas , Charles L. Seitz, Multicomputers: Message-Passing Concurrent Computers, Computer, v.21 n.8, p.9-24, August 1988 [doi>10.1109/2.73]
• DBMS79: Dongarra, J.J., Bunch, J.R.,Moler, C.B., and Stewart, G.W., Linpack Users' Guide, SIAM, Philadelphia, 1979.
• DuER86: Iain S Duff , Albert M Erisman , John K Reid, Direct methods for sparse matrices, Oxford University Press, Inc., New York, NY, 1986
• EgKL88: Egecioglu, O., Koc, C.K. and Laub, A.J., "A Recursire Doubling Algorithm for Solution of Tridiagohal Systems on Hypercube Multiprocessors," Technical Report No. TRC88-1, Dept. of Computer Science, Univ. of California, Santa Barbara, 1988.
• GrRe86: Gmnwald, M.R. and Reed, D.A., "Benchmarking Hypercube Hardware and Software," Technical Report, UIUCDCS-R-86-1303, Department of Computer Science, University of Illinois at Urbana-Champaign, 1986.
• Hell78: Heller, D., "A Survey of Parallel Algorithms in Numerical Algebra," SIAM Review, Vol. 20, pp. 740-777, Oct. 1978.
• Hock65: R. W. Hockney, A Fast Direct Solution of Poisson's Equation Using Fourier Analysis, Journal of the ACM (JACM), v.12 n.1, p.95-113, Jan. 1965 [doi>10.1145/321250.321259]
• Hwan87: Hwang, K., "Advanced Parallel Processing with Supercomputer Architectures," Proc. of the IEEE, pp. 33-47, Oct. 1987.
• John87a: S. Lennart Johnsson, Solving tridiagonal systems on ensemble architectures, SIAM Journal on Scientific and Statistical Computing, v.8 n.3, p.354-392, May 1, 1987 [doi>10.1137/0908040]
• John87b: S. Lennart Johnsson, Communication effect basic linear algebra computations on hypercube architectures, Journal of Parallel and Distributed Computing, v.4 n.2, p.133-172, April 1, 1987 [doi>10.1006/jpdc.1997.1353]
• MiVo88: Michielse, P.H. and Vorst, H.A., "Data Transport in Wang's Partition Method," Parallel Computing, 7, North-Holland, pp.87-95, 1988.
• Nuge88: S. F. Nugent, The iPSC/2 direct-connect communications technology, Proceedings of the third conference on Hypercube concurrent computers and applications: Architecture, software, computer systems, and general issues, p.51-60, January 19-20, 1988, Pasadena, California, United States [doi>10.1145/62297.62305]
• OrVo85: Ortega, J.M. and Voigt, R.G., "Solution of Partial Differential Equations on Vector and Parallel Computers,'' SIAM Review, pp. 149-240, June 1985.
• RaNi88: Ramanatha_n, J. and Ni, LgtI., "The Mapping Problem: Revisited," Technical Report, MS U-CPS- ACS-IO, Dec. 1988.
• SaSc85: Saad, Y. and Schultz, M.H., "Data Communication in Hypercube," Research Report, YALEU/DCS/RR- 428, Oct. 1985.
• ShMo49: Sherman, J., and Morrison, W.J., "Adjustment of an Inverse Matrix Corresponding to Changes in the Elements of a Given Colunm or a Given row of the Original Matrix," Ann. Math. Stat. 20, 621.1949.
• Smit85: Smith, G.D., Numerical Solution of Partial Differential Equations, Oxford University Press, 1985.
• Ston73: Harold S. Stone, An Efficient Parallel Algorithm for the Solution of a Tridiagonal Linear System of Equations, Journal of the ACM (JACM), v.20 n.1, p.27-38, Jan. 1973 [doi>10.1145/321738.321741]
• SuSN89: Sun, X.H., Sun, H.Z., and Ni, L.M., "Parallel Algorithms for Solution of Tridiagonal Systems on Multicomputers," Technical Report MSU-CPS.ACS-1I, Department of Computer Science, Michigan State University. Feb. 1989.
• Wang81: H. H. Wang, A Parallel Method for Tridiagonal Equations, ACM Transactions on Mathematical Software (TOMS), v.7 n.2, p.170-183, June 1981 [doi>10.1145/355945.355947]
• Wood50: Woodbury, M., "Inverting Modified Matrices," Memorandum 42, Statistics Research Group, Princeton, New Jersey. 1950.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

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

General Terms:
Algorithms, Design, Experimentation, Measurement, Performance, Theory