Accession Number : AD0736962

Title :   On the Number of Multiplications Required to Compute Quadratic Functions,

Corporate Author : CORNELL UNIV ITHACA N Y DEPT OF COMPUTER SCIENCE

Personal Author(s) : Vari,Thomas Michael

Report Date : JAN 1972

Pagination or Media Count : 32

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)

Descriptors :   (*MATHEMATICAL PROGRAMMING, ALGORITHMS), (*COMPUTER PROGRAMMING, FUNCTIONS(MATHEMATICS)), ALGEBRA, RINGS(MATHEMATICS), COMPLEX VARIABLES, TRANSFORMATIONS(MATHEMATICS)

Subject Categories : Operations Research

Distribution Statement : APPROVED FOR PUBLIC RELEASE