Accession Number:

AD0736962

Title:

On the Number of Multiplications Required to Compute Quadratic Functions,

Descriptive Note:

Corporate Author:

CORNELL UNIV ITHACA N Y DEPT OF COMPUTER SCIENCE

Personal Author(s):

Report Date:

1972-01-01

Pagination or Media Count:

32.0

Abstract:

The paper is a study of the number of multiplications required for the evaluation of quadratic functions in n variables. Several sufficient conditions are presented for a requirement of j multiplications. A procedure is given for generating the optimal program for any quadratic function over a noncommutative ring. An application of these results solves an open problem posed by Knuth. Necessary and sufficient conditions are found for real and complex functions to require j multiplications. Author

Subject Categories:

  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE