Please use this identifier to cite or link to this item: http://hdl.handle.net/1880/46600
Title: ON THE COMPLEXITY OF BILINEAR FORMS OVER ASSOCIATIVE ALGEBRAS
Authors: Bshouty, Nader H.
Keywords: Computer Science
Issue Date: 1-Dec-1989
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.
URI: http://hdl.handle.net/1880/46600
Appears in Collections:Bshouty, Nader

Files in This Item:
File Description SizeFormat 
1989-373-35.pdf2.04 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.