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

Johnson, Rodney W.; Mcloughlin, Aileen M.

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

Active / Technical Report | Accession Number: ADA069451 |

Open PDF

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 Ladermans in a sense that is made precise. Author

Author(s):

Johnson, Rodney W. ; Mcloughlin, Aileen M.

Author Organization(s):

NAVAL RESEARCH LAB WASHINGTON DC

Descriptive Note:

Final rept.,

Pagination:

0013

Security Markings

DOCUMENT & CONTEXTUAL SUMMARY

Distribution:

Approved For Public Release

RECORD

Collection: TR

Identifying Numbers

Report Number(s):

NRL-MR-3994

Task Number(s):

RR0140941

Project Number(s):

RR01409

Subject Terms

Communities of Interest:

No COI(s) Identified

Descriptor(s):

*MATRICES(MATHEMATICS), ALGORITHMS, COMPUTATIONS, COEFFICIENTS, POLYNOMIALS, SEARCHING, COMPUTER APPLICATIONS

Field(s)/Group(s):

Theoretical Mathematics

Keyword(s):

PE61153N, WUB0235

Report Date:

1979 May 07