Publication
Journal of Algorithms
Paper

On systems of bilinear forms whose minimal division-free algorithms are all bilinear

View publication

Abstract

In this paper we prove that for a certain class of systems of bilinear forms, all minimal division-free algorithms are essentially bilinear. This class includes systems for computing products in finite algebraic extension fields, and systems for computing the products of Toeplitz and Hankel matrices with vectors. Our results, together with the classification theorems of S. Winograd (Theoret. Comput. Sci. 8 (1979), 359-377; Math. Systems Theory 10 (1977), 169-180) completely describe all minimal division-free algorithms for computing these systems. We also prove, as an immediate consequence of our results, that the multiplicative complexity of the quaternion product over a real field is 8. © 1981.

Date

Publication

Journal of Algorithms

Authors

Share