ON THE COMPLEXITY OF BILINEAR FORMS OVER ASSOCIATIVE ALGEBRAS

Abstract

Let $F$ be a field and let $Q( alpha )~=~q sub 1 sup {d sub 1} ( alpha )... q sub k sup {d sub k} ( alpha )~(mo~F[ alpha ]$ be a polynomial of degree $n$ where $q sub 1 ( alpha ),...,q sub k ( alpha )$ are distinct irreducible polynomials. Let $y sub 1 ( alpha ),...,y sub r ( alpha ),~x sub 1 ( alpha ),...,x sub 3 ( alpha )$ be $r~+~s,~n~-~$1-degree polynomials. It is shown that if $Card(F)~>=~max sub {1 <=i<=k}~2deg~q sub i sup d sub i ( alpha )~-~2$ then the number of nonscalar multiplications/divisions required to compute the coefficients of $x sub i ( alpha ) y sub 1 ( alpha )~ mod~Q( alpha ),~i=1,...,s$ by straight line algorithms is $ s(2n~-~k) $. We also prove that if $H$ is an $s~times~r$ matrix with entries from $F$ then the number of nonscalar multiplications/divisions required to compute the coefficients of $(x sub 1 ( alpha ),...,x sub s ( alpha ))H(y sub 1 ( alpha ), ...,y sub r ( alpha )) sup T $ by straight line algorithms is $ rank(H)(2n~-~k)$. All those systems satisfy the direct sum conjecture strongly. For some other algebras that are direct sum of local algebras the above results also hold.