ALGORITHMS FOR MATRIX MULTIPLICATION

Abstract

Strassen's and Winograd's algorithms for matrix multiplication are investigated and compared with the normal algorithm. Floating - point error bounds are obtained, and it is shown that scaling is essential for numerical accuracy using Winograd's method. In practical cases Winograd's method appears to be slightly faster than the other two methods, but the gain is, at most, about 20%. An attempt to generalize Strassen's method is described.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1970
Accession Number
AD0705509

Entities

People

  • R. P. Brent

Organizations

  • Stanford University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Accuracy
  • Algorithms
  • Arithmetic
  • Binary Arithmetic
  • Computational Complexity
  • Computer Science
  • Computers
  • Error Analysis
  • Errors
  • Floating Point Operations
  • Identities
  • Iterations
  • Lepidoptera
  • Military Research
  • Notation
  • Numbers
  • Precision

Readers

  • Computer Programming and Software Development.
  • Theoretical Analysis.