Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
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 Free Access

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

DOI: http://dx.doi.org/10.1090/S0025-5718-1974-0331751-8
PII: S 0025-5718(1974)0331751-8
Keywords: LU decomposition, Strassen's method, fast matrix inversion, linear equations, Gaussian elimination, computational complexity
Article copyright: © Copyright 1974 American Mathematical Society