Efficient parallel solution of linear systems

ABSTRACT

The most efficient known parallel algorithms for inversion of a nonsingular n × n matrix A or solving a linear system Ax = b over the rationals require &Ogr;(log n)2 time and M(n)n0.5 processors (where M(n) is the number of processors required in order to multiply two n × n rational matrices in time &Ogr;(log n).) Furthermore, all known polylog time algorithms for those problems are unstable: they require the calculation to be done with perfect precision; otherwise they give no results at all. This paper describes parallel algorithms that have good numerical stability and remain efficient as n grows large. In particular, we describe a quadratically convergent iterative method that gives the inverse (within the relative precision 2-nO(1)) of an n × n rational matrix A with condition ≤ n0(1) in &Ogr;(log n)2 time using M(n) processors. This is the optimum processor bound and the factor n0.5 improvement of known processor bounds for polylog time matrix inversion. It is the first known polylog time algorithm that is numerically stable. The algorithm relies on our method of computing an approximate inverse of A that involves &Ogr;(log n) parallel steps and n2 processors. Also, we give a parallel algorithm for solution of a linear system Ax = b with a sparse n × n symmetric positive definite matrix A. If the graph G(A) (which has n vertices and has an edge for each nonzero entry of A) is s(n)-separable, then our algorithm requires only &Ogr;((log n)(log s(n))2) time and |E| + M(s(n)) processors. The algorithm computes a recursive factorization of A so that the solution of any other linear system Ax = b′ with the same matrix A requires only &Ogr;(log n log s(n)) time and |E| + s(n)2 processors.

REFERENCES

• 1: Atkinson, K. E., An Introduction to Numerical Analysis, Wiley, New York (1978).
• 2: Stuart J. Berkowitz, On computing the determinant in small parallel time using a small number of processors, Information Processing Letters, v.18 n.3, p.147-150, March 1984 [doi>10.1016/0020-0190(84)90018-8]
• 3: Bodewig, E., Matrix Calculus, Second Edition, Interscience Publishers, Inc., New York; North-Holland Company, Amsterdam (1959).
• 4: Bojanczyk, A., "Complexity of Solving Linear Systems in Different Models of Computation", SIAM J. on Numerical Analysis 21(3), 591-603 (1984).
• 5: Borodin, A., J. von zur Gathen, and J. Hopcroft, "Fast Parallel Matrix and GCD Computations", Information and Control 52(3), 241-256 (1982).
• 6: Borodin, A. and I. Munro, The Computational Complexity of Algebraic and Numeric Problems, American Elsevier, New York (1975).
• 7: Chandra, A. K., "Maximal Parallelism in Matrix Multiplication", Report RC-6193, I.B.M. Watson Research Center, Yorktown Heights, New York (October 1976).
• 8: Coppersmith, D. and S. Winograd, "On the Asymptotic Complexity of Matrix Multiplication", SIAM J. on Computing 11(3), 472- 492 (1982).
• 9: Csanky, L., "Fast Parallel Matrix Inversion Algorithms", SIAM J. on Computing 5(4), 618-623 (1976).
• 10: George, J. A., "Nested Dissection of a Regular Finite Element Mesh", SIAM J. on Numerical Analysis 10(2), 345-367 (1983).
• 11: Hageman, L. and D. Young, Applied Iterative Methods, Academic Press, New York (1981).
• 12: Hotelling, H., "Some New Methods in Matrix Calculation", Ann. Math. Statist. 14, 1-34 (1943a).
• 13: Hotelling, H., "Further Points on Matrix Calculations and Simultaneous Equations", Ann. Math. Statist. 14, 440-441 (1943b).
• 14: Householder, A., The Theory of Matrices in Numerical Analysis, Blaisdell Publishing Co., New York (1964).
• 15: Isaacson, E. and H. B. Keller, Analysis of Numerical Methods, Wiley, New York (1966).
• 16: Lipton, R., D. Rose, and R. E. Tarjan, "Generalized Nested Dissection", SIAM J. on Numerical Analysis 16(2), 346-358 (1979).
• 17: Lipton, R. J. and R. E. Tarjan, "A Separator Theorem for Planar Graphs", SIAM J. on Appl. Math. 36, 177-189 (1979).
• 18: Newman, M., "Matrix Computation", Survey of Numerical Analysis, 222-255, (S. Todd, Ed.), McGraw Hill, New York (1982).
• 19: Victor Pan, How to multiply matrices faster, Springer-Verlag New York, Inc., New York, NY, 1984
• 20: Pan, V. and J. H. Reif, "Efficient Parallel Solution of Linear Systems", Tech. Report TR-02-85, Center for Research in Computer Technology, Aiken Computation Laboratory, Harvard Univ. (1985).
• 21: Preparata, F. P. and D. V. Sarwate, "An Improved Parallel Processor Bound in Fast Matrix Inversion", Information Processing Letters 7(3), 148-149.
• 22: Schultz, G., "Iterative Berechnung der Reziproken Matrix", Z. Angew. Math. Mech. 13, 57-59 (1933).
• 23: Strassen, V., "Vermeidung von Divisionen", J. Reine Angew. Math. 164, 184-202 (1973).
• 24: Valiant, L., S. Skyum, S. Berkowitz, and C. Rackoff, "Fast Parallel Computation of Polynomials Using Few Processors", SIAM J. on Computing 12(4), 641-644 (1983).
• 25: Varga, R. S., Matrix Iterative Analysis, Prentice-Hall (1962).
• 26: J. H. Wilkinson, The algebraic eigenvalue problem, Oxford University Press, Inc., New York, NY, 1988
• 27: Young, D. M., Iterative Solution of Large Linear Systems, Academic Press, New York (1971).

INDEX TERMS

Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.0 General
          Subjects: Parallel algorithms
  G.2 DISCRETE MATHEMATICS

General Terms:
Algorithms, Theory, Verification