Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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



Triangular factorization and inversion by fast matrix multiplication

Authors: James R. Bunch and John E. Hopcroft
Journal: Math. Comp. 28 (1974), 231-236
MSC: Primary 65F30
MathSciNet review: 0331751
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The fast matrix multiplication algorithm by Strassen is used to obtain the triangular factorization of a permutation of any nonsingular matrix of order n in $ < {C_1}{n^{{{\log }_2}7}}$ operations, and, hence, the inverse of any nonsingular matrix in $ < {C_2}{n^{{{\log }_2}7}}$ operations.

References [Enhancements On Off] (What's this?)

  • [1] G. E. Forsythe & C. B. Moler, Computer Solution of Linear Algebraic Equations, Prentice-Hall, Englewood Cliffs, N.J., 1967. MR 36 #2306. MR 0219223 (36:2306)
  • [2] A. S. Householder, The Theory of Matrices in Numerical Analysis, Blaisdell, New York, 1964. MR 30 #5475. MR 0175290 (30:5475)
  • [3] V. Strassen, "Gaussian elimination is not optimal," Numer. Math., v. 13, 1969, pp. 354-356. MR 40 #2223. MR 0248973 (40:2223)
  • [4] R. S. Varga, Matrix Iterative Analysis, Prentice-Hall, Englewood Cliffs, N.J., 1962. MR 28 #1725. MR 0158502 (28:1725)
  • [5] S. Winograd, Private communication.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65F30

Retrieve articles in all journals with MSC: 65F30

Additional Information

Keywords: LU decomposition, Strassen's method, fast matrix inversion, linear equations, Gaussian elimination, computational complexity
Article copyright: © Copyright 1974 American Mathematical Society

American Mathematical Society