Computer-Aided Discovery of a Fast Matrix-Multiplication Algorithm.

Abstract

A computer program was written that searches for fast matrix-multiplication algorithms by seeking roots of a certain multivariate polynomial. An algorithm was discovered that, like the one discovered by Laderman, uses 23 noncommutative multiplications in multiplying 3-by-3 matrices. The new algorithm is demonstrably inequivalent to Laderman's in a sense that is made precise. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 07, 1979
Accession Number
ADA069451

Entities

People

  • Aileen M. Mcloughlin
  • Rodney W. Johnson

Organizations

  • United States Naval Research Laboratory

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Coefficients
  • Computational Complexity
  • Computations
  • Computer Programs
  • Computers
  • Information Systems
  • Military Research
  • Numbers
  • Permutations
  • Polynomials
  • Rational Numbers
  • Real Numbers

Readers

  • Educational Psychology
  • Fluid Dynamics.
  • Mathematical Modeling and Probability Theory.