ON THE NUMBER OF MULTIPLICATIONS NECESSARY TO COMPUTE CERTAIN FUNCTIONS

Abstract

The number of multiplications and divisions required in certain computations is investigated. In particular, results of Pan Motzkin, about polynomial evaluation as well as similar results about the product of a matrix by vector, are obtained. As an application of the results on the product of a matrix by vector, a new algorithm for matrix multiplication, which requires about 1/2(n cubed) multiplications, is obtained.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Nov 15, 1968
Accession Number
AD0696645

Entities

People

  • Shmuel Winograd

Organizations

  • IBM Thomas J. Watson Research Center

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Computational Complexity
  • Computations
  • Mathematical Analysis
  • Mathematics
  • Military Research
  • Polynomials
  • Test And Evaluation
  • Three Dimensional
  • Two Dimensional

Fields of Study

  • Mathematics

Readers

  • Linear Algebra