DocumentCode :
332933
Title :
Multiplicative complexity of Taylor shifts and a new twist of the substitution method
Author :
Schonhage, A.
Author_Institution :
Inst. fur Inf. II, Bonn Univ.
fYear :
1998
fDate :
8-11 Nov 1998
Firstpage :
212
Lastpage :
215
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;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 1998. Proceedings. 39th Annual Symposium on
Conference_Location :
Palo Alto, CA
ISSN :
0272-5428
Print_ISBN :
0-8186-9172-7
Type :
conf
DOI :
10.1109/SFCS.1998.743445
Filename :
743445
Link To Document :
بازگشت