Title :
Multiplicative complexity of Taylor shifts and a new twist of the substitution method
Author_Institution :
Inst. fur Inf. II, Bonn Univ.
Abstract :
Let Cn=Cn(K) denote the minimum number of essential multiplications/divisions required for shifting a general n-th degree polynomial A(t)=Σaiti to some new origin x, which means to compute the coefficients bk of the Taylor expansion A(x+t)=B(t)=Σbktk as elements of K(x,a0,...,an) with indeterminates a i and x over some ground field K. For K of characteristic zero, a new refined version of the substitution method combined with a dimension argument enables us to prove Cn⩾n+[n/2]-1 opposed to an upper bound of Cn⩽2n+[n/2]-4 valid for all n⩾3
Keywords :
computational complexity; Taylor shifts; multiplicative complexity; nth degree polynomial; substitution method; upper bound; Costs; Ear; Polynomials; Upper bound;
Conference_Titel :
Foundations of Computer Science, 1998. Proceedings. 39th Annual Symposium on
Conference_Location :
Palo Alto, CA
Print_ISBN :
0-8186-9172-7
DOI :
10.1109/SFCS.1998.743445