<\body> <\doc-data||<\doc-author-data||<\author-address> LIX, CNRS École polytechnique 91128 Palaiseau Cedex France ||> \; |<\doc-note> This work has been supported by the ANR-09-JCJC-0098-01 project, as well as a Digiteo 2009-36HD grant and Région Ile-de-France. > \; ||> <\abstract> In this paper, we study the complexity of several basic operations on linear differential operators with polynomial coefficients. As in the case of ordinary polynomials, we show that these complexities can be expressed in terms of the cost of multiplication. Let > be an effective field of constants of characteristic zero, so that all field operations can be carried out by algorithms. Given an indeterminate and the derivation =x*\>, where =\/\ x>, we will study various operations in the skew ring |]>>, such as multiplication, division, greatest common divisors, series solutions, etc. In analogy with the commutative case, we will give bounds for the computational complexities of these operations in terms of the complexity of operator multiplication. For our complexity measures, it is convenient to assume that all field operations can be carried out in constant time >. We will try to express the complexities of our algorithms in terms of the following standard complexities: <\itemize> The time > required for the multiplication of two polynomials of degrees>n> and coefficients in >. It is classical that =O> and =O*> if > admits sufficiently many >-th roots of unity. The complexity >|)>> of multiplying two r> matrices with entries in >. It is classical that \2.376>, although \3> in practice. We will denote by > the subset of > of polynomials of degree n>. Likewise, we denote by |]>> the set of operators \|]>> of degree L\n> in and degree > L\r> in >. Now consider two linear differential operators \|]>>. We start with studying the following complexities: <\itemize> The complexity > of multiplying and . The complexity > of applying to a vector of polynomials in >. The cost > to compute a fundamental system of solutions to the monic equation +L|)> f=0> in |]>>, up to order |)>>, while assuming the existence of such afundamental system. Given a vector of truncated power series in >, the cost >> of computing a monic operator in +\|]>> with =O|)>>. The special case was first studied in, where it was shown that =O>|)>>, using evaluation-interpolation techniques. The inverse bound >=O|)>> has been proved in; this paper also contains detailed information on the constant factors involved in these bounds. For fixed constants ,\\0>, we notice that *n|)>=O|)>>, *r|)>>=O>|)>>, *n,\*r|)>>=O|)>>, etc. In this paper, we will freely use this remark without further mention. In order to simplify our complexity estimates, it will be convenient to make a few additional assumptions. First of all, we will assume that \2>, whence in particular *log n=\-1>|)>>. We will also assume that the function /n> is increasing and that />> is increasing in both and . This will indeed be the case for the complexity bounds for > that will be given in section. In section, we will first prove (see theorems and) that the problems of multiplication and operator-vector application are essentially equivalent whenr>. In section, we recall the best available bounds in the case when r>. It remains an open question whether these bounds are optimal. In section, we show that the problems of computing fundamental systems of solution and its inverse can be reduced to operator multiplication modulo a logarithmic overhead (see theorems and). This provides a dual way to perform operations on differential operators by working on their fundamental systems of solutions. In section, we start with the operations of exact division and division with remainder. In section, we consider greatest common divisors and least common multiples. Again, we will show how to express the complexities of these operations essentially in terms of the complexity > of multiplication(see theorems, , and ). To the best of our knowledge, the idea to perform operations on linear differential operators power series solutions was first proposed (but only partially worked out) in. We were independently aware of this possibility and prefer the use of fundamental systems of solutions (so as to force a clean bijection between operators and solution spaces). It is also possible to mimic classical divide and conquer algorithms for division, greatest common divisors and least common multiples, while using adjoints in order to perform the recursive operations on the appropriate side. Such algorithms were implemented inside and we plan to analyze them in a forthcomingpaper. The key argument behind the proof from that =O>|)>> is the observation that an operator \|]>> is uniquely determined by its images on the vector =,x|)>>>. This makes it possible to use a similar evaluation-interpolation strategy for the multiplication of differential operators as in the case of FFT-multiplication of commutative polynomials. More precisely, given \|]>>, let > be the matrix of the mapping \\;P\L> with respect to the bases > and >: <\eqnarray*> >||>|>||)>>>|>||>>|>|>||)>>>>>>.>>>> <\lemma> Let \|]>>. Then <\enumerate-alpha> We may compute > as a function of in time *log r|)>>. We may recover from > in time *log r|)>>. <\proof> Consider the expansion of with respect to <\eqnarray*> |)>>|||)>+\+x*L|)>.>>>> For all , we have <\eqnarray*> |)>|)>>||*L|)>|]>|)>>>|||*L+j|)>|]>>>|||.>>>> In other words, > is a lower triangular band matrix <\eqnarray*> >||>||>|>|>|>|>||>>||>|>>|||>>>>>>>>> of bandwidth n>. The coefficients on the -th subdiagonal of > are exactly the result of amultipoint evaluation of > at ,r-1>. It is classical that both multipoint evaluation and the inverse operation of interpolation can be performed in time *log r|)>>. Doing this for each of the polynomials ,\,L> yields the result. <\theorem> If r>, then <\eqnarray*> >||+n**log r|)>>>>> <\proof> Let \|]>> and assume that we want to compute . We may evaluate |)>> in time ,2*r|)>>=O|)>>. We may also evaluate |)>|)>> in time >=O|)>>. Using the lemma, we may recover from |)>|)>> in time *log r|)>>. This completes the proof. <\theorem> If r>, then <\eqnarray*> >||+n**log r|)>.>>>> <\proof> Assume now that we are given |)>\\|]>>, as well as a vector ,\,V|)>>\\> and that we want to evaluate =|)>,\,K|)>|)>>. This is equivalent to evaluating the operator >=K-r|)>> at the vector *V>. It is classical that >> can be computed in time |)>>. Using the lemma, we may compute the unique operator \|]>> with |)>=x*V> in time **log r|)>=O*log r|)>>. We may next compute the product >*L> in time >=O|)>>. The lemma finally allows us to evaluate >*L> at > in time *log r|)>>, thereby yielding >. Let us review the best know algorithms (asymptotically speaking, and up to constant factors) for the multiplication of linear differential operators and for the evaluation of linear differential operators at vectors of polynomials. We will treat the cases r> and n> separately. r>> <\theorem> If r>, then <\eqnarray*> >||*r|)>.>>>> <\proof> Consider two operators K*x*\,L=L*x*\\\|]>>. Then we may compute their operator product using the formula <\eqnarray*> ||*|\ \>|)> K\|\ x>|)> L,>>>> attributed to Takayama, where <\eqnarray*> L>||,j>K*L,j>*x>*\>>>>> denotes the commutative product of and . Commutative products can be computed in time |)>> using Kronecker substitution, whence the result follows. In practice, it is often possible and best to compute the commutative products using bivariate FFT multiplication. In that case several of the FFT-transforms can be shared. For instance, ifr>, then the most expensive step is to compute the > transforms with respect to of the coefficients in > of the first derivatives /\ x|)> L>. For large , this optimization yields an algorithm of complexity *M*r>. <\theorem> If r>, then <\eqnarray*> >||*min|)>.>>>> <\proof> This is a direct consequence of theorems and. In practice, in the domain where FFT-multiplication is most efficient, it is better to use a more direct method to obtain this result. Given \|]>>> and \>, we use the following algorithm: <\itemize> Compute the > FFT-transforms of V> with r> and the FFT-transforms of the coefficients of with respect to >. From these values, deduce the FFT-transforms of the entries of > using scalar r> matrix-vector multiplications. Recover > using inverse transforms. This algorithm has a complexity *M*r>, for large . If >|)>>, then the following result becomes more efficient for the evaluation of linear differential operators at vectors of polynomials: <\theorem> If r>, then we have <\eqnarray*> >||*r-2>|)>.>>>> <\proof> We may cut both and into > pieces in |]>> and >. Hence =O*|)>=O*r-2>|)>>. Here we repeatedly use the commutation rule |)>*x=x*L+k|)>>>, when considering |)>> and > as operators. The twist |)>\L+k|)>>> can be computed in time |)>>, for \|]>> . If both >|)>>, this yields the following more efficient algorithm for the multiplication of linear differential operators: <\theorem> If r>, then we have <\eqnarray*> >||*r-2>|)>.>>>> <\proof> Direct consequence of theorems and. We recall from that >=O|)>>. More generally, we have: <\theorem> If r>, then the product of an n> matrix and an r> matrix with coefficients in > can be computed in time |)>>. <\proof> By the result from, the problem is equivalent to the computation of |n/r|\>> operators ,\,K> in |]>> with a fixed operator |]>>>. Setting +x*K+\+x>*K>, we may compute in time |)>>. We may directly read off the products *L,\,K*L> from the result. <\remark> An interesting open problem at the time of writing concerned the existence of a better bound for > than the one given in theorem. In collaboration with Benoit and Bostan, we have recently been able to prove the sharper bound =O-1>*n+r**log n|)>> for the case when r>. n>> <\theorem> If n>, then <\eqnarray*> >||*n|)>.>>>> <\proof> Let \|]>> and consider the expansion <\eqnarray*> |)>>|||)>+\+x*L|)>>>>> of in >. Then we have <\eqnarray*> ||)>*L|)>>||n>K|)>**L|)>|)>>>|||n>x*K+k|)>*L|)>>>>> For each , both the Taylor shift +k|)>> and the product +k|)>*L|)>> can be computed in time *n|)>> . <\theorem> If n>, then <\eqnarray*> >||-1>*r|)>.>>>> <\proof> Let \|]>> and \>. We may compute |)>> in time -1>*r|)>>, since this really amounts to the computation of > matrix products of sizen>. Writing > for a constant r> matrix , we may thus compute =M*L|)>> in time -1>*r|)>>. <\theorem> If n>, then <\eqnarray*> >||-1>*r+n**log r|)>>>>> <\proof> Let \|]>>. By lemma, we may compute > and > in time *log r|)>>. Since both of these matrices are band matrices of bandwidths n>, we may compute the product <\eqnarray*> >||*\>>>> in time -1>*r|)>>. Again by lemma, we may reconstruct from > in time *log r|)>>. From now on, we will assume that r>. We recall that an operator \|]>> of order is said to be at >, if its leading coefficient > does vanishes at >. We will say that an operator \|]>> of order is non singular (at the origin) if r>*L\|]>>> and *L> is non singular as an operatorin>. Given a non singular differential operator \|]>> of order , the equation =0> admits a fundamental system ,\,H|)>>> of solutions in |]>>, with the property that |)>=1> and |)>=0> for all r>> with j>. Conversely, given a >-linearly independent vector of power series \|]>>, there exists aunique monic operator \+\|]>|]>> of order with =0>. Let us show how to convert efficiently between these two representations. <\theorem> Let \|]>> be a differential operator of order , which is non singular at the origin, and let be its canonical fundamental system of solutions. Then we may compute up to order |)>> in time *log n|)>>. In other words, <\eqnarray*> >||*log n|)>.>>>> <\proof> Modulo multiplying on the left by 1>>, we may assume without loss of generality that is monic. Since is non singular at the origin, we have *L\\|]>>. Rewritten in terms of >, this means that is of the form <\eqnarray*> |||)>+x*C*\|)>+\+x*C*\|)>.>>||)>>||*-1|)>*\*-k+1|)>,>>>> for certain ,\,C\\>. Setting |)>-L\x*\|]>>, we observe that maps |]>> into *\|]>>. We now compute using the ``recursive'' formula <\eqnarray*> ||>|>>|>>>>>+\|)>|)>,>>>> where <\eqnarray*> |)>r>A*x|)>>||r>|\>*x.>>>> The equation() is a schoolbook example for applying the strategy of relaxed resolution of power series equations. Since |)>> operates coefficientwise, it can be computed in linear time. The main cost of the computation therefore reduces to the relaxed evaluation of >. Using fast relaxed multiplication, this amounts to a cost <\eqnarray*> >|||n/2|\>,r|)>+4*|n/4|\>,r|)>+\+n*.>>>> Using the monotonicity assumption and theorem, the result follows. In what follows, given a non zero series in , we denote by > its valuation. Given a vector of elements in a >-vector space, we will also denote by > the subvector space generated by the entries of , and <\eqnarray*> >||:Y\Vect\|}>.>>>> <\theorem> Let ,\,H|)>\\|]>> be >-linearly independent. Then there exists a unique monic operator \\+\|]>|]>> with =0>. Moreover, given the truncation of at order |)>>, we may compute at order >|)>> in time *log r|)>>. In other words, <\eqnarray*> >||*log r|)>.>>>> <\proof> Modulo a triangularization of , we may assume without loss of generality that |)>\\\v|)>=v>. We define operators >,\,L>> by <\eqnarray*> >>||>|>>||- L>|)>|L>|)>>|)>*L>.>>>> Then >> annihilates and for any other operator \\+\|]>> with =0>, we would have -L|)>=0>, which is in contradiction with the fact that -L|)>\r>. Moreover, by induction over , we observe that the coefficient of > in >> is given by -v|)>|)>*\*-v|)>|)>> and the coefficients of ,\,x> in >> can be expressed in terms of the coefficients of ,\,x|)>>> in ,\,H>. In particular, the truncation of at order >|)>> is uniquely determined by the truncation of at order |)>>. In order to explicitly compute up to a given order, it is more efficient to use a divide and conquer approach. More precisely, given ,\,H|)>\\> we compute \\+\|]>> using the following method: <\itemize> If , then we take =\- H/H|)> mod x>. Otherwise, let with |r/2|\>>. Compute ann,\,H|)>>. Evaluate |)>,\,A|)>|)> mod x>. Compute ann,\,I|)>>. Return >. If v>, then it is easy to check that =O>|)>>. For a fixed constant , we thus have <\eqnarray*> >|>|+C*.>>>> The result now follows from the monotonicity assumption. <\remark> If /r>> is increasing in for some \0>, then the bound further simplifies to =O|)>>. <\remark> We notice that the operator in theorem is singular if and only if =r-1>, and if and only if :Y\Vect\|}>=,r-1|}>>. Although a general operator \|]>> can be singular at the origin, many operations on operators (such as division and greatest common divisors) commute with translations x+x>, and the following lemmas can be used in order to reduce to the case when is non singular at the origin. <\lemma> Any operator \|]>> can be rewritten as an operator in |]>> in time |)>>. Similarly, an operator x*\|]>> may be rewritten as an operator in |]>> in time |)>>. <\proof> In, it is shown how to perform these rewritings using matrix products, so that the result follows from theorem. <\lemma> Given a non zero operator \|]>>, we may find a point \\> where is non singular in time |)>>. <\proof> Let > be the leading coefficient of . Since L\n>, we have |)>\0> for some \,n|}>>. Using fast multipoint evaluation, we may find such a point > in time |)>>. From the formula() it is clear that both the degrees in and > are additive for the multiplication of operators \|]>>>. In particular, if \|]>> and is left or right divisible by , then the quotient is again in |]>>. <\theorem> Let \|]>> be such that for some \|]>>. Then we may compute in time *log n|)>>. <\proof> By lemmas and, and modulo ashift x+x>, we may assume without loss of generality that and are non singular at the origin. We now use the following algorithm: <\itemize> We first compute the canonical fundamental system of solutions to =0>> up to order |)>>. By theorem , this can be done in time *log n|)>>>. We next evaluate > and compute a>-basis for > at order |)>>. This can be done in time |)>>, by theorems and, and using linear algebra. Since is non singular, we have \deg> K\v|)>=v> for all \|]>>. In particular, the > Q=deg> L-deg> K> elements of of valuations > K,\,deg> L-1> are mapped to set which spans a vector space of dimension > Q>. This shows that mod x|)>=deg> Q>. We now compute the monic annihilator =ann> of at order |)>>. This can be done in time *log r|)>=O*log n|)>>, by theorem. We return the truncation of *\> at order |)>>, where =L> L>/K> K>>. Since each of the steps can be carried out in time *log n|)>>, the result follows. It is classical that euclidean division generalizes to the skew polynomial ring |]>>. In other words, given operators \|]>> where 0>, there exist unique operators > and > in |]>> with <\eqnarray*> ||>>> and > R\deg> B>. If \|]>> and is the leading term of with respect to >, then left multiplication of by > A-deg> B+1>> allows us to remain in the domain |]>>>: there exist unique > and > in |]>> with <\eqnarray*> > A-deg> B+1>*A>||>>>> and > R\deg> B>. The operators and are usually called pseudo-quotients and pseudo-remainders. In some cases, a non trivial polynomial can be factored out in the relation(). Let be monic, of maximal degree, such that *Q*B,J1>*R\\|]>>. Then we call 1>*Q=quo>> and 1>*R=rem>> the ``simplified'' pseudo-quotient and pseudo-remainder of and . <\lemma> Let ,\,H|)>\\|]>> be >-linearly independent and define |)>+1>. Given *\|]>|)>>, there exists a unique operator \|]>|]>> of order r> with =G> and we may compute its first terms with respect to in time *log n|)>>. <\proof> Let =v|)>> for each . Modulo a base change, we may assume without loss of generality that \\\\>. Let :\|]>\\|]>> be the operator with <\eqnarray*> ,\,V|)>>||>*V,\,x>*V|)>,>>>> and let > denote the inverse operator. Let :\|]>|]>\\|]>> be the operator with <\eqnarray*> >||1>|)>|)>.>>>> Writing K*x*\> and =|)>>, we have <\eqnarray*> >>|>>|>>>>>>|||>|>||)>>>|>|>||>>||>|>||)>>>>>>>*>>|>>|>>>>>.>>>> In other words, > and its inverse > operate coefficientwise and coefficients can be computed in time >*n|)>>. Putting =x>+E> with =o>|)>> for each , we may rewrite the equation =G>as <\eqnarray*> ||1>|)>|)>>>>> and we observe that the coefficient of > in the righthand side of() only depends on earlier coefficients of ,x> in . In particular, we may solve the equation using a relaxed algorithm. Then the main cost is concentrated in the relaxed evaluation of >. As in the proof of theorem, this evaluation can be done in time *log n|)>>. <\theorem> Let \|]>> with r> and > K\0>. Skew pseudo-division of by and simplification yields a relation <\eqnarray*> ||>>> where >,R=rem>\\|]>>. If \n> is such that \|]>,r>>>, then and can be computed in time ,r|)>*log n|)>>. <\proof> Modulo a shift x+x>, we may assume without loss of generality that and are non singular at the origin. We now use the following algorithm: <\itemize> We compute the canonical fundamental system of solutions to =0> up to order+r>|)>>. This requires a time ,s|)>*log n|)>>. We compute > with =A*G> up to order +r>|)>>. This requires atime ,r|)>|)>>. We determine the operator \\|]>|]>> with =x*G> up to order +r>|)>>. The lemma shows that this can be done in time ,s|)>*log n|)>>. By theorem, we have *A*\> and s>*\> is known up to order >|)>>. Now s>*\,\,x*\> are truncated rational functions, for which the degrees of the numerators and denominators are bounded by >. Using rational function reconstruction, we may thus compute /D=x*\> with ,D|)>=1> in time *log n|)>>>. Taking ,\,D|)>>, we find . Once and are known, we compute using the algorithm from theorem. The total complexity of this algorithm is bounded by ,r|)>*log n|)>>. <\remark> In the above proof, we have assumed that > is known beforehand. In general, we may still apply the above algorithm for a trial value>>. Then the algorithm may either fail (for instance, if ,\,D|)>\n>>), or return the triple > under the assumption that \|]>>,r>>. We may then check whether the triple is correct in time >,r|)>|)>>. Applying this procedure for successive guesses >=n,2*n,4*n,\>, the algorithm ultimately succeeds for an >> with >\2*n>. Using the monotonicity hypothesis, the total running time thus remains bounded by >,r|)>*log n>|)>=O,r|)>*log n|)>>. It is classical that greatest common divisors and least common multiples exist in the skew euclidean domain |]>>: given two operators \|]>>>, the greatest common divisor =gcd> and the least common multiple =lcm> are the unique monic operators with <\eqnarray*> |]>*\>|||]>*K+\|]>*L>>||]>*\>|||]>*K\\|]>*L.>>>> Assume now that \|]>> and let and be monic polynomials of minimal degrees, such that > and > are in |]>>. Then we call >=gcd>=A*\> and >=>>=B*\> the (simplified) pseudo-gcd and pseudo-lcm of and . <\theorem> Let \|]>> and \n> be such that >=gcd>\\|]>,r>>. Assume that , and >> are non singular at the origin. Then we may compute>> in time ,r|)>*log n|)>>. <\proof> We compute >> using the following algorithm: <\itemize> We compute the canonical fundamental systems of solutions and to =0> and =0> at order +2*r>|)>>. This can be done in time ,r|)>*log n|)>>. Using linear algebra, we compute a basis for \Vect> at order +2*r>|)>>. This can be done in time n*r-1>|)>>. Since >=lcm>> is non singular, we have +Vect|]> mod x|)>=deg> \>=deg> G+deg> H-deg> \>>. Hence, |)>=dim mod x|)>+ mod x|)>>-dim +Vect|]> mod x|)>=deg> \>>. We compute =ann=gcd> at order >|)>>. By theorem, this can be done in time ,r|)>*log n|)>>. We compute >> from mod x>> using rational function reconstruction. This algorithm requires a running time ,r|)>*log n|)>>.\ <\remark> In the above proof, we have again assumed that > is known beforehand. Below, we will discuss ways to check the correctness of the computed result for a trial value>>, after which a similar strategy as in remark can be applied. During the relaxed computation of and , we may also check whether > at each next coefficient. In the particular case when =1>, the running time of the algorithm will then be bounded by >,r|)>*log n>|)>>, where >> is the smallest order at which common solutions no longer exist. This kind of early termination only works for this very special case. <\remark> Notice that >> might be singular at the origin, even if , and >>> are not. This happens for instance when is the minimal annihilator of the vector > and the minimal annihilator of the vector ,x|)>>, so that =\-1>. <\theorem> Let \|]>> and \n> be such that >=lcm>\|]>,r>>>. If , and >> are non singular at the origin, then we may compute >> in time ,r|)>*log n|)>>. <\proof> Similar to the proof of theorem, by taking +Vect> instead of \Vect>. <\remark> The above algorithms can be generalized to gcds and lcms of more than two operands. This is usually more efficient than the repeated computation of gcds or lcms ofpairs. The assumption that >> should be non singular is still a bit unsatisfactory in theorems and, even though the probability that a randomly chosen point is singular is infinitesimal. \ If we drop this assumption, then we still have deg> \>> in the proof of theorem. Consequently, ``candidate'' pseudo-gcds >> found by the algorithm are genuine pseudo-gcds whenever >> pseudo-divides both and . Using the division algorithms from the previous section, this can be checked in time *r,r|)>*log n|)>> in the case of gcds and *log n|)>> in the case of lcms. An alternative way to check whether candidate gcds and lcms are correct is to compute Bezout and Ore relations. More precisely, given \|]>> with \*K>, there exist operators \\|]>> with <\eqnarray*> >>|>>>>>|||>||>>>>*>|>>>>,>>>> > A*K,deg> B*L\deg> \> and >. The 2> matrix at the righthand side will be called the Euclidean matrix =Eucl> of and . In a similar way as above, we may define a (simplified)pseudo-Euclidean matrix >=Eucl>> with entries >,B>,C>,D>>> in |]>>, whenever \|]>>. We will say that > is non singular at >, if the denominators of and do not vanish at >. <\theorem> Let \|]>> and \n> be such that >=Eucl>\|]>,r>2>>>. If , , >> and > are non singular at the origin, then we may compute >> in time ,r|)>*log n|)>>. <\proof> Assuming > known, we compute =|>||>>>>> at order >|)>> as follows: <\itemize> We compute the canonical fundamental systems of solutions and to =0> and =0> at order +3*r>|)>>. We compute a basis for \Vect> at order +3*r>|)>>, together with bases > and > for the supplements of > in > >. We also compute =ann> at order +2*r>|)>>. We solve the systems |)>|)>=\|)>> and |)>|)>=\|)>> in at order >|)>>, using lemma. We compute a basis for +Vect> at order +2*r>|)>>, as well as bases > and > for the vector spaces |)>> |)>> at order +2*r>|)>>. We compute > K>*ann|)>> and > L>*ann|)>> at order >|)>>. We finally compute >> from and using rational function reconstruction. The complexity analysis and the remainder of the proof is done in a similar way as in the proofs of theorems and. With the above techniques, we may at least verify whether computed pseudo-gcds or pseudo-lcms are correct. For a fully deterministic algorithm, we still need away to find a point where >> is non singular. This can be done by brute force. Let us state the result for pseudo-gcds; similar deterministic results hold for pseudo-lcms and pseudo-Euclidean matrices. <\theorem> Let \|]>> and \n> be such that >=gcd>\\|]>,r>>. Then we may compute >> in time *r,r|)>*log n+n**r+r>|)>|)>>. <\proof> Let > K>, > L>, and assume first that we know >. Then, at +1> distinct random points where and are non singular, we compute canonical fundamental systems of solutions and at order |)>>. This can be done in time **r+r>|)>|)>>>. We now pick a point at which the dimension of +Vect|)> mod x> is maximal and apply the algorithm from theorem in order to find >>. If > is unknown, then we use a sequence of guesses =n,2*n,4*n,\>, as in the previous proofs. <\bibliography|bib|tm-plain|all.bib> <\bib-list|18> A.V.Aho, K.SteiglitzJ.D.Ullman. Evaluating polynomials on a fixed set of points. , 4:533--539, 1975. A.BorodinR.T.Moenck. Fast modular transforms. , 8:366--386, 1974. A.Bostan. . , École polytechnique, 2003. A.BostanÉ.Schost. Polynomial evaluation and interpolation on special sets of points. , 21(4):420--446, August 2005. Festschrift for the 70th Birthday of Arnold Schönhage. AlinBostan, FrédéricChyzakNicolas LeRoux. Products of ordinary differential operators by evaluation and interpolation. J. RafaelSendraLaureanoGonzález-Vega, , 23--30. Linz/Hagenberg, Austria, July 2008. ACM. D.G.CantorE.Kaltofen. On fast multiplication of polynomials over arbitrary algebras. , 28:693--701, 1991. J.W.CooleyJ.W.Tukey. An algorithm for the machine calculation of complex Fourier series. , 19:297--301, 1965. D.CoppersmithS.Winograd. Matrix multiplication via arithmetic progressions. > Annual Symposium on Theory of Computing>, 1--6. New York City, may 25--27 1987. J. von zurGathenJ.Gerhard. . Cambridge University Press, 2-nd, 2002. R.T.MoenckA.Borodin. Fast modular transforms via division. , 90--96. Univ. Maryland, College Park, Md., 1972. V.Pan. , 179 Springer, 1984. V.PanD.Bini. . Birkhauser, 1994. V.Strassen. Gaussian elimination is not optimal. , 13:352--356, 1969. V.Strassen. Die Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten. , 20:238--251, 1973. J.van derHoeven. FFT-like multiplication of linear differential operators. , 33(1):123--127, 2002. J.van derHoeven. Relax, but don't be too lazy. , 34:479--542, 2002. J.van derHoeven. Relaxed multiplication using the middle product. ManuelBronstein, , 143--147. Philadelphia, USA, August 2003. J.van derHoeven, G.Lecerf, B.Mourain etal. Mathemagix. 2002. <\with|font-family|tt> http://www.mathemagix.org . <\initial> <\collection> <\references> <\collection> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > <\auxiliary> <\collection> <\associate|bib> CK91 CT65 Str69 Pan84 CW90 vdH:FFT BCR08 Bos:phd vdH:mmx vdH:FFT MB72 Str73 BM74 ASU75 PB94 GaGe02 ASU75 BCR08 BCR08 ASU75 vdH:relax vdH:issac03 vdH:FFT BCR08 BoSc05 GaGe02 <\associate|toc> |math-font-series||font-shape||1.Introduction> |.>>>>|> |math-font-series||font-shape||2.Evaluation and interpolation> |.>>>>|> |math-font-series||font-shape||3.Basic complexity bounds> |.>>>>|> |3.1.Large degrees |n\r> |.>>>>|> > |3.2.Large orders |r\n> |.>>>>|> > |math-font-series||font-shape||4.Local solutions> |.>>>>|> |math-font-series||font-shape||5.Division> |.>>>>|> |math-font-series||font-shape||6.Euclidean operations> |.>>>>|> |math-font-series||font-shape||Bibliography> |.>>>>|>