On the Number of Multiplications Required to Compute Quadratic Functions
Vari, Thomas Michael
This 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 non-commutative ring. An application of these results solves an open problem possed by Knuth. Necessary and sufficient conditions are found for real and complex functions to require $j$ multiplications.
computer science; technical report
Previously Published As