ON THE COMPLEXITY OF BILINEAR FORMS OVER ASSOCIATIVE ALGEBRAS
Date
1989-12-01
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
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.
Description
Keywords
Computer Science