Computational Complexity of Inner Products of Vectors (And That of Other Bilinear Forms) over a Noncommutative Ring (Auxiliary Functions Allowed)
Robert Mandl, Thomas Vari · SIAM Journal on Computing · 1975
We prove that the minimum number of ring multiplications necessary to compute the inner product of two n-vectors over a noncommutative ring is n, even if any number of auxiliary functions (each being a polynomial in the elements of exactly one of the vectors) are allowed “for free”. This is the “noncommutative” analogue of a result of Winograd’s stating that the minimum number of multiplications needed to compute the inner product over a commutative ring is n, if auxiliary functions are not allowed, and, respectively, $ \approx (n/2)$, if auxiliary functions are allowed. More generally, given a bilinear form whose matrix is ${\bf S}$, the minimum number of multiplications necessary to compute it over a noncommutative ring is $\operatorname{rank} ({\bf S})$, whether or not auxiliaries are allowed. The method used is a modification of Floyd’s linear algebra approach : the inner product ${\bf x} \cdot {\bf y}$ (or any other bilinear form) is regarded as a quadratic form in the $2n$ indeterminates $x_1 , \cdots ,x_n ,\, y_1 , \cdots ,y_n $ (rather than as a bilinear form in the two separate sets of n indeterminates). The same method can also be applied to bilinear forms over commutative rings; when the form is the inner product, the method yields an improved lower bound, thereby closing the difference between Winograd’s achievable upper bound $\lceil n/2 \rceil $ and his proven lower bound $\lfloor n/2 \rfloor $. Another result of Winograd’s, that the minimum number of binary operations necessary for computing the inner product is $2n - 1$ (even if auxiliary functions are allowed), can also be extended to noncommutative rings.