A practical parallel algorithm for solving band symmetric positive definite systems of linear equations

ABSTRACT

We give a practical parallel algorithm for solving band symmetric positive definite systems of linear equations in O(m* log n) time using nm/log n processors. Here n denotes the system size and m its bandwidth. Hence, the algorithm is efficient. For tridiagonal systems, the algorithm runs in O(log n) time using n/log n processors. Furthermore, an improved version runs in O(log m log n) time using nm2/(log m log n) processors.

REFERENCES

• 1: Ilan Bar-on , Uzi Vishkin, Optimal parallel generation of a computation tree form, ACM Transactions on Programming Languages and Systems (TOPLAS), v.7 n.2, p.348-357, April 1985 [doi>10.1145/3318.3478]
• 2: CSANK~, L. Fast parallel matrix inversion algorithms. SIAM J. Comput. 5, 4 (Dec. 1976), 618-623.
• 3: DONGARRA, J. J., AND SAMEH, A.H. On some parallel banded systems solvers. Parallel Comput. 1 (1984), 223-235.
• 4: EBERLY, W. Very fast parallel matrix and polynomial arithmetic. In Proceedings of the 25th FOCS Conference (1984), 21-30.
• 5: Zvi Galil*, Optimal parallel algorithms for string matching, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.240-248, December 1984 [doi>10.1145/800057.808687]
• 6: Alan George , Joseph W. Liu, Computer Solution of Large Sparse Positive Definite, Prentice Hall Professional Technical Reference, 1981
• 7: GOLUB, G. H., AND VAN LOAN, C.F. Matrix Computations. Johns Hopkins University Press, Baltimore, Md., 1983.
• 8: 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]
• 9: HELLER, D. A survey of parallel algorithms in numerical linear algebra. SIAM Rev. 20, 4 (Oct. 1978), 740-777.
• 10: HOSHINO, T., KAMIMURA, T., IIDA, T., AND SHIRAKAWA, T. Parallelized ADI scheme using GECR (Gauss-Elimination-Cyclic-Reduction) method and implementation of Navier-Stokes equation in the PAX computer, in Proceedings of the 26th FOCS Conference (1985), 426-433.
• 11: KUMAR, S. P., AND KOWALICK, J.S. Parallel factorization of a positive definite matrix on an MIMD computer. Proceedings of the 1984 ICPP (1984), 410-416.
• 12: D H. Lawrie , A H. Sameh, The computation and communication complexity of a parallel banded system solver, ACM Transactions on Mathematical Software (TOMS), v.10 n.2, p.185-195, June 1984 [doi>10.1145/399.401]
• 13: MEIER, U. A parallel partition method for solving banded systems of linear equations. Parallel Comput. 2 (1985), 33-43.
• 14: ORTEGA, J.M. Numerical Analysis, A Second Course. Academic Press, New York, 1972.
• 15: V Pan , J Reif, Efficient parallel solution of linear systems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.143-152, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22161]
• 16: Udo Schendel, Introduction to Numerical Methods for Parallel Computers, Prentice Hall PTR, Upper Saddle River, NJ, 1984
• 17: SHmOACH, Y., AND VISHKIN, U. Finding the maximum merging and sorting in parallel computation model. J. Algorithms 2, 1 (1981), 88-102.
• 18: 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]
• 19: STRANG, G. Linear Algebra and Its Applications. Academic Press, New York, 1980.
• 20: VALIANT, L. G. Parallelism in comparison problems. SIAM J. Comput. 4, 3 (Sept. 1975), 348-355.
• 21: VISHKIN, U. Synchronous parallel computation--a survey. TR-71, Dept. of Computer Science, Courant Institute, New York, Univ., 1983.
• 22: WEAVER, H., JR., AND JOHNSTON, P.R. Finite Elements for Structural Analysis. Prentice-Hall, Englewood Cliffs, N.J., 1984.
• 23: WINO, O., AND HUANG, J.W. A computational model of parallel solution of linear equations. IEEE Trans. Comput. C-29, 7 (1980), 632-638.

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); Matrix inversion

General Terms:
Algorithms, Performance, Theory