> <\body> of multivariate polynomials>|>|<\doc-note> This paper is part of a project that has received funding from the French \PAgence de l'innovation de défense\Q. ||<\author-affiliation> CNRS, École polytechnique, Institut Polytechnique de Paris Laboratoire d'informatique de l'École polytechnique (LIX, UMR 7161) Bâtiment Alan Turing, CS35003 1, rue Honoré d'Estienne d'Orves 91120 Palaiseau, France |>>||<\author-affiliation> CNRS, École polytechnique, Institut Polytechnique de Paris Laboratoire d'informatique de l'École polytechnique (LIX, UMR 7161) Bâtiment Alan Turing, CS35003 1, rue Honoré d'Estienne d'Orves 91120 Palaiseau, France |>>||<\doc-note> > The evaluation of a polynomial at several points is called the problem of multi-point evaluation. Sometimes, the set of evaluation points is fixed and several polynomials need to be evaluated at this set of points. Several efficient algorithms for this kind of \Pamortized\Q multi-point evaluation have been developed recently for the special cases of bivariate polynomials or when the set of evaluation points is generic. In this paper, we extend these results to the evaluation of polynomials in an arbitrary number of variables at an arbitrary set of points. We prove a softly linear complexity bound when the number of variables is fixed. > Let > be an effective field, so that we have algorithms for the field operations. Given apolynomial \,\,X|]>> and a tuple =,\,\|)>>\|)>> of points, the computation of |)>\|)>,\,P|)>|)>\\> is called the problem of . This problem naturally occurs in several areas of applied algebra. When solving apolynomial system, multi-point evaluation can for instance be used to check whether all points in a given set are indeed solutions of the system. In, we have shown that efficient algorithms for multi-point evaluation actually lead to efficient algorithms for polynomial system solving. Bivariate polynomial evaluation has also been used to compute generator matrices of algebraic geometry error correcting codes. In the univariate case when , it is well known that one may use so-called \Premainder trees\Q to compute multi-point evaluations in quasi-optimal time. More precisely, if > stands for the cost to multiply two univariate polynomials of degree d> (in terms of the number of field operations in >), then the multi-point evaluation of a polynomial of degree d> at points can be computed in time *log d|)>>. Using a variant of the Schönhage\UStrassen algorithm, it is well known that =O>. If we restrict our attention to fields > of positive characteristic, then we may take =O> d>|)>> and conjecturally even =O>. In the remainder of this paper, we make the customary hypothesis that /d> is a non-decreasing function in . Currently, the fastest general purpose algorithm for multivariate multi-point evaluation is based on the \Pbaby-step giant-step\Q method; see 3>. For afixed dimension and > P+1|)>> such that >, this method requires -1>*D|)>> operations in> ( by taking =\> and =\> in 3.3>). Here |)>> is a common abbreviation for *|)>>|)>>, and \1.5> is a constant such that two\> and \n> matrices with coefficients in > can be multiplied using >|)>> operations in >. The best known theoretical bound is \1.629>2, half of the upper bound for >> (combined with the tensor permutation lemma7>). In the special case when , >, and > P=deg> P>, Nüsken and Ziegler proved the sharper bound +1|)>/2>|)>>4>. In 2008, Kedlaya and Umans achieved a major breakthrough. On the one hand, they gave an algorithm of complexity >> for the case when > has positive characteristic. On the other hand, they gave algorithms for multi-point evaluations over/r*\> with quasi-optimal bit-complexity exponents. Unfortunately, to the best of our knowledge, these algorithms do not seem suitable for practical purposes, as observed in. Even in the case when the dimension is fixed, we also note that the algorithms by Kedlaya and Umans do not achieve a smoothly linear complexity of the form >>. Recently, several algorithms have been proposed for multi-point evaluation in the case when > is a fixed tuple of points. These algorithms are in the sense that we allow for potentially expensive precomputations as a function of >. The algorithms from are both restricted to the case when > is sufficiently generic, whereas focus on the bivariate case . In the present paper, we deal with the general case when both and > are arbitrary. Our main result is the following: <\theorem> Let 1> be a fixed dimension and let \|)>> be a fixed set of points. Then, given a polynomial \,\,X|]>> with > P+1|)>\d> and an element of > of multiplicative order at least *n!*>, we can compute |)>=|)>,\,P|)>|)>> using <\equation*> O*+*|)> operations in >. <\remark> In characteristic zero, any integer different from , , and has infinite order. For finite fields >, working in an algebraic extension>> yields elements of order up to -1>. Replacing > by such an extension induces an additional overhead of > in our complexity bound. As in the generic case from, our algorithm heavily relies on the relaxed algorithm for polynomial reduction from. Given polynomials ,\,B>\\,\,X|]>>, the reduction algorithm computes ,\,Q>,R\\,\,X|]>> with <\eqnarray*> ||*B+\+Q>*B>+R,>>>> where is reduced with respect to some admissible ordering > on monomials. The relaxed algorithm from essentially performs this reduction with the same complexity (up to a logarithmic factor) as checking the relation. For our application to multi-point evaluation, the idea is to pick the polynomials > in the vanishing ideal <\equation*> \>>\,\,X|]>\A|)>=\|}> of >, so |)>=R|)>>. We may next recursively split-up the tuple of points > into two halves and adopt a similar strategy as in the univariate case. However, there are several technical problems with this idea. First of all, it would be too costly to work with a full Gröbner basis ,\,B>|}>> of >>, because the mere storage of such a basis generally requires more than > terms. In, we solved this issue by working with respect to a so called \Paxial basis\Q instead. In the case when > is not generic, we have the additional problem that the shape of a Gröbner basis may become very irregular. This again has the consequence that the mere size of all products*B> in may exceed >. In this paper, we address these problems by introducing the new technique of . The idea is to work with several orderings on the monomials; in particular, each > belongs to a Gröbner basis for >> with respect to a different admissible ordering. The result of a quasi-reduction is usually not reduced with respect to any usual Gröbner basis of >>, but we will still be able to control the size of . Moreover, during the quasi-reduction process, we will be able to ensure that the ratios <\equation*> deg> Q\\\deg> Q and <\equation*> deg> B\\\deg> B are similar for every , which further allows us to control the size of the products *B>. The constant factor in our complexity bound of Theorem grows exponentially as afunction of . For the time being, we therefore expect our methods to be of practical use only in low dimensions like or . Of course, the present paper focuses on worst case bounds for potentially highly non-generic cases. There is hope to drastically lower the constant factors for more common use cases. One major technical contribution of this paper is the introduction of quasi-reduction and heterogeneous orderings. An interesting question for future work is whether these concepts can be applied to other problems. For instance, consider a zero-dimensional ideal \\,\,X|]>> and two Gröbner bases for > with respect to different monomial orderings. Each Gröbner basis induces a representation for elements of the quotient algebra ,\,X|]>/\>. Does there exist a smoothly linear time algorithm to convert between these two representations? In this section we recall and extend some results from to the context of this paper. Let > be the set of monomials >*\*X>> with ,\,a\\>. Any polynomial \,\,X|]>>> can uniquely be written as a linear combination <\eqnarray*> ||\>P*M>>>> with coefficients > in > and finite <\eqnarray*> |>|\\P\0|}>.>>>> Given a total ordering> on>, the support of any non-zero polynomial admits aunique maximal element =lm>\\> that is called the of ; the corresponding coefficient =lc>=P>\\> is called the of . A total ordering > on> is said to be if <\equation*> M\N>M\NM\N>X*M\X*N for all monomials \>> and ,n|}>>. In particular, the lexicographical ordering> defined by <\eqnarray*> >*\*X>\X>*\*X>>|>|\b>|>>|=b\a\b>|>>|>|>|=b\\\a=b\a\b>|>>>>>>>> is admissible. A of a polynomial in ,\,X|]>> is a data structure that stores the set of the non-zero terms of. Each such term is a pair made of a coefficient and adegree vector. In an algebraic complexity model the bit size of the exponents counts for free, so the relevant size of such a polynomial is the cardinality of its support. Consider two polynomials and of ,\,X|]>> in sparse representation. An extensive literature exists on the general problem of multiplying and ; see for a recent survey. For the purposes of this paper, a superset > for the support of will always be known. Then we define > to be the cost to compute , where is the maximum of the sizes of> and the supports of and . We will assume that /s> is anon-decreasing function in . Under suitable assumptions, the following proposition will allow us to take =O*log s|)>> in our multivariate evaluation algorithm. <\proposition> Let ,\,\> be positive integers and let > in > be of multiplicative order at least \\*\*\>. <\enumerate-roman> The set > of all products >*\*\>*\*\*\*\*\>> for ,\,e|)>\,\-1|}>> can be computed using |)>> operations in >. Let and be in ,\,X|]>>, in sparse representation. Let > be a superset of the support of with > M\\> for all \> and ,n>. Assume that > has been precomputed. Then the product> can be computed using *log s|)>> operations in >, where denotes the maximum of the sizes of > and the supports of and . <\proof> The first statement is straightforward. The second one is an adapted version of6>. We assume that the reader is familiar with the technique of relaxed power series evaluations, which is an efficient way to solve so-called recursive power series equations. In, this technique was generalized to multivariate Laurent series that are expanded according to some admissible ordering >. Given a general admissible ordering >, we know from that there exist real vectors ,\,\\\>, such that <\eqnarray*> \X>|>|\i>\X\j>,>>>> where <\eqnarray*> >|>|>*\*X>>>|\i>|>|\i,\,\\i|)>.>>>> For clarity we sometimes denote this ordering > by >>. In, it is always assumed that ,\,\\\> and |)>,\,|)>|)>=1> for all . <\example> The graded lexicographical ordering > is obtained by taking =,1|)>>>, =,0|)>>, =,0,|)>>, >, =,0,1,0|)>>. <\example> In section, we will only need orderings for which =>,\,2>|)>> for certain ,\,a\\> and =,0|)>,\=,0|)>,\,\=,0,1,0|)>>. In fact, we note that >>=>>> for any \>>, so modulo the replacement of > by ,\,a|)>>*\>, we may assume without loss of generality that ,\,a\\>, whenever we wish to apply the theory from. In order to analyze the complexity of relaxed products in this multivariate context, we need to introduce the following quantities for finite subsets \\>: <\eqnarray*> |)>>||\e\X\\|}>+1,i=1,\,n>>||)>>|||)>*\*\|)>.>>>> We also define ,i>|)>\\|)>> and >|)>\\|)>> when we need to emphasize the dependence on >. <\theorem> 3>> Given sparse polynomials \,\,X|]>> and a set > with *\\>, the relaxed product can be computed in time <\equation*> O|\|>|)>*log|)>|)>|)>. Let > be a total ordering on > and consider a finite family |)>I>> of non-zero polynomials in ,\,X|]>>. Each > comes with a distinguished monomial \supp B> (that will play the role of the leading monomial) and we define \|)>>*L>. The family |)>I>> is equipped with a , that is a function <\eqnarray*> :\>|>|>>> For each I>, we also assume that we have fixed the set \L*\> of monomials that will be selected for reduction with respect to>, for I>. We assume that the > are pairwise disjoint and we set <\eqnarray*> >|>|I>\.>>>> Note that this corresponds to fixing a selection strategy, although we do require that \I>L*\> (which explains the terminology \Pquasi-reduction\Q below). For our application later in this paper, the complement \I>L*\|)>> will be a \Prather relatively small\Q finite set. We say that \,\,X|]>> is if \=\>. We say that a total ordering > on > is (with respect to our choices of |)>I>>, |)>I>> and the selection strategy >) if N\M\N> for all \> and if <\eqnarray*> >*B|)>>|>|>>> for any I> and any \>. Polynomials that are not quasi-reduced are said to be . In order to quasi-reduce \,\,X|]>> with respect to |)>I>> we may use Algorithm below. This yields the relation <\eqnarray*> ||I>Q*B+R,>>>> such that is quasi-reduced with respect to |)>I>>. We call|)>I>,R|)>> the of with respect to |)>I>>. <\specified-algorithm> <\description-compact> and a finite family |)>I>> with a selection strategy >. The extended quasi-reduction |)>I>,R|)>> of by |)>I>>.\ <|specified-algorithm> <\enumerate> Initialize P> and \0> for all I>. While \=\> do: <\enumerate> Let be the largest monomial of \>; Replace >> by >+*M|T>>>; Replace by *M|T>>*B>>. Return |)>I>,R|)>>. By construction, we have <\eqnarray*> *L|)>>|>|>>>> for all I>. The main contribution of is a relaxed algorithm for the computation of extended reductions. This algorithm generalizes to our setting as follows and provides an alternative for Algorithm with a better computational complexity. For each ,+1|}>>, let > be the -th canonical basis vector <\equation*> e\|\>,0,1,0,\,0|)>>+1>. We first define the operator > on monomials: <\eqnarray*> :\>|>|,\,X|]>+1>>>||>|>>*e>,M\\>>||>|+1>.>>>> By linearity we next extend > to ,\,X|]>>: <\equation*> \\>P*M|)>\\>P*\. Let >\B-T>. By construction, we have <\eqnarray*> |)>I>,R|)>>||I>Q*B>|)>,>>>> which allows us to regard |)>I>,R|)>> as a fixed point of the operator <\eqnarray*> |)>I>,R|)>>|>|I>Q*B>|)>.>>>> This operator is \Precursive\Q in the sense of4.2> with respect to the ordering>. Consequently |)>I>,R|)>> can be computed efficiently using relaxed power series evaluation. The complexity of this relaxed quasi-reduction is stated in Theorem below for the specific ordering used by our multi-point evaluation algorithm. This definition and study of this ordering is the purpose of the next section. An is an -tuple =,\,w|)>\>|)>> with *\*w=1>. Given amonomial >*\*X>>, we define its >-degree> by <\eqnarray*> > X>*\*X>>||*e+\+w*e.>>>> For a non-zero polynomial \>P*M\\,\,X|]>>, we define its >-degree> by <\eqnarray*> > P>||> M\P\0|}>.>>>> We also define the ordering >> on > by <\eqnarray*> >N>|>|> M\deg> N|)>\> M=deg> N\M\N|)>.>>>> It is easy to check that >> is an admissible ordering. Consider a zero-dimensional ideal > of ,\,X|]>> and let <\equation*> d>dim> \,\,X|]>/\. Given an admissible weight >, there exists a unique non-zero polynomial >> in the reduced Gröbner basis of > whose leading monomial is minimal for >> and whose leading coefficient is one. We call>> the >-simplest element> of >. Note that there are at most monomials below the leading monomial of >> for >>. <\proposition> Let <\equation*> \>|n> and consider the set ,\>> of monomials \>> with > M\\>. Then ,\>|\|>\d>. <\proof> Let ,\>\\> be the set of exponents of ,\>>, so we have <\equation*> \,\>>*\*X>\,\,e|)>\\,\>|}>. The set ,\>+> in particular contains the simplex <\equation*> \>,\,e|)>\>|)>\w*e+\+w*e\\|}>, whose volume is given by <\eqnarray*> >|||n!*w*\*w>|n!>d+1.>>>> Consequently, ,d>|\|>=,d>|\|>=vol ,\>+|)>\vol \=d+1>. <\corollary> For each ,n|}>>, we have <\eqnarray*> > B>>|>||w>.>>>> <\proof> We say that \\> is an > for>> if >M\N\\> for all \> and \>. By definition, the set ,\>> is an initial segment for >> and it contains at least monomials. Consequently, the set of linear combinations of monomials in ,\>> contains at least one non-zero element of > and therefore >>. Now consider a monomial >*\*X>> in >\\,\>>. Then *e\deg> X>*\*X>\\>> for ,n>, whence \\/w>. Now consider a finite non-empty set > of admissible weights. Given amonomial \>>, we define its >-degree>> M> by <\eqnarray*> > M>|>|\\> deg> M.>>>> For a non-zero polynomial \>P*M\\,\,X|]>>, we define its >degree>by <\eqnarray*> > P>|>|> M\P\0|}>.>>>> We define the >> by <\eqnarray*> >N>|>|> M\deg> N|)>\> M=deg> N\M\N|)>.>>>> <\lemma> The ordering >> verifies N\M\>N> for all different \>. <\proof> For all \> we have > M\deg> N>, whence > M\deg> N>. <\example> Consider , =,|}>>. With > and > we have <\eqnarray*> > M>||=1>>|> N>||=1>>|>*M|)>>||=3>>|>*N|)>>||=2.>>>> Therefore > M\deg> N> but >*M|)>\deg>*N|)>>, which shows that the ordering >> is not admissible. Given \\>, its associated >\\> is defined by <\eqnarray*> >>|>|\\deg> M=deg> M|}>.>>>> By construction, we have <\eqnarray*> >||\\>\>,>>>> but this union is not necessarily disjoint. Given >*\*X>\\>>, we note that *e>*\*X*e>\\>> for any \\>> with |\*e,\,\*e|\>\\>; this explains the terminology\Pcone\Q. Let > again be a zero-dimensional ideal of ,\,X|]>> and let dim> \,\,X|]>/\>. Let > be a finite non-empty set of weights that will play the role of the index set from section. For \\>, let >> be the >-simplest element of > and let <\eqnarray*> >>|>|>>>|)>.>>>> We also define <\eqnarray*> >|>|*\*X.>>>> We endow > with the lexicographical ordering > and fix the following selection strategy: for increasing \\>, we set <\eqnarray*> >>|>|L>*\\\*M\\>|}>\\\>\>|)>.>>>> Now consider the total ordering >>> on > that is defined by <\eqnarray*> >>N>|>|*M\>\*N,>>>> for all \>. We call >>> a . The shift of all exponents by one (through multiplication by >) is motivated by the fact that the product of the partial degrees of a monomial in *\> never vanishes. This will be important in the next section in order to establish certain degree bounds. <\proposition> The ordering >>> is quasi-admissible. <\proof> Consider \\> and \>>, so that <\eqnarray*> > \*M>||> \*M.>>>> Given supp B>>, we need to prove that <\eqnarray*> \>>*N>|>>>|>>> Now >=lm>>>|)>> implies >L>>, whence *U\>\*M>. In particular, > \*U\deg> \*M> and *U\\*M> whenever > \*U=deg> \*M>. If > \*U=deg> \*U>, then it follows that > \*U\deg> \*M> or > \*U=deg> \*M> and *U\\*M>, whence *U\>\*M> and >>M>>. Otherwise, <\equation*> > \*U=deg> \*U\deg> \*U\deg> \*M=deg> \*M> for some \\\|}>>>, whence *U\>\*M> and >>M>. In this section we instantiate the weight family > considered in the previous section, and analyze the complexity of the corresponding quasi-reduction. Consider a zero-dimensional ideal > of ,\,X|]>> and let dim> \,\,X|]>/\>. In order to devise an efficient algorithm to quasi-reduce polynomials with respect to >, our next task is to specify a suitable set of weights >. We take =\>, with <\eqnarray*> >|>|>,\,2>|)>\,\,e|)>\\,e+\+e=0,2|\|>>\D,\,2|\|>>\D|}>>>>> and where d> depends on the degree of the polynomials that we wish to reduce. <\lemma> We have <\eqnarray*> |\|>>|>| D+1|)>.>>>> <\proof> Consider ,\,e\\> with +\+e=0> and |\|>>\D,\,2|\|>>\D>. We have \|log D|\>,\,|log D|\>|}>> for ,n-1> and > is determined uniquely in terms of ,\,e> by =-+\+e|)>>. There are at most |log D|\>+1|)>> ways to pick ,\,e> in this manner. Assume that =\> for some max>. We associate a selection procedure and a quasi-admissible ordering to > as in section. <\lemma> Let =,\,w|)>\\> and >*\*X>\\> with *M\\>> and +1|)>>*\*+1|)>\D>. Then for all ,n|}>>>, we have <\eqnarray*> *+1|)>>|>|*+1|)>.>>>> <\proof> Assume the contrary and let be the index for which *+1|)>> is maximal. Similarly, let be the index for which *+1|)>> is minimal, so that *+1|)>\2*w*+1|)>>. Since <\equation*> *+1|)>|]>*\**+1|)>|]>=+1|)>*\*+1|)>>D, we have *+1|)>\>. In particular, since 4> we have \\D/2>. If \1>, then there must exist at least one index i> with \2> and <\equation*> w*+1|)>>w*+1|)>>2. Since +1\D>, this yields \2/D>. If \1> then w/2\D>, since 2>. In both cases we consider the weight =,\,w|)>> with =w/2>, =2*w>, and =w> for all ,n|}>\>. By what precedes, we have \\>. We now verify that <\eqnarray*> > \*M-deg> \*M>||-w|)>*+1|)>+-w|)>*+1|)>>>|||**+1|)>-w*+1|)>|)>>>||>|>>> This contradicts our assumption that *M\\>>, > \*M=deg> \*M>. <\corollary> Let ,n|}>>. With the notations from Lemma and <\eqnarray*> >>|>|+1|)>*\*+1|)>|n>-1,>>>> we have <\equation*> >+1|2*w>\e+1\>+1|)>|w>\|w>.> <\proof> Lemma implies <\equation*> >+1|)>=*+1|)>|]>*\**+1|)>|]>\*+1|)>|)>,> but also <\equation*> *+1|)>|)>\*+1|)>|]>*\**+1|)>|]>=>+1|)>|)>.> The result follows by extracting -th roots. We define ,\,X|]>> to be the set of polynomials \,\,X|]>> such that +1|)>*\*+1|)>\D>> for all >*\*X>\supp P>. Given \,\,X|]>>, let us now examine the complexity of extended quasi-reduction. <\theorem> Given \,\,X|]>> with d>, we may compute its extended quasi-reduction <\eqnarray*> ||\\>Q>*B>+R>>>> using <\equation*> O*|)> operations in > (for any fixed value of ). In addition, for all \\>, we have <\eqnarray*> >>*B>|)>+1|)>>|>|*n!*.>>>> <\proof> We solve using the relaxed approach from, recalled in section. However, contrary to the situation in, each individual product >*B>> is computed in a relaxed manner with respect to a different ordering (namely, >>). More precisely, for each individual product >*B>>, we recall from that <\eqnarray*> >*supp Q>>|>|>.>>>> So we can actually compute >*B>> using the relaxed product algorithm from Theorem with respect to the ordering >>. Here we note that the supports of >> and >> are contained in dense blocks of similar proportions: for ,n>, Corollary yields <\eqnarray*> > B>>|>||n>|w>,>>>> whereas Corollary implies <\eqnarray*> > Q>+1>|>||w>.>>>> Indeed, for any >*\*X>\supp Q>>, we have >*M\\>>, whence *M\\>> and +1\2*/w>. Let >> be the set of monomials >*\*X>> with \deg>>*Q>|)>> for ,n>>, so that >*Q>|)>\\>> and <\eqnarray*> >|\|>>|>|>>*Q>|)>+1|)>.>>>> Using *\*w=1>, we deduce that\ <\eqnarray*> >>*Q>|)>+1|)>>||> B>+> Q>+1|)>|)>>>||>||n>|w>+|w>|)>>>||||n>+2*|)>>>||>|2*|)>*|n>>>||>|*max|)>*>>||>|*n!*.>>>> It particular, as a side remark, we note that the dense multiplication of >> and >> can be done using >|\|>|)>=O|)>> operations in >. As to the relaxed product of >> and >>, we first note that >>=>>>, with the notation from Example, where >,\,2>|)>=2*,\,w|)>> with ,\,a\\> and \D>. Consequently, <\eqnarray*> >,1>>|)>>||i\n>2>*O|w>|)>O|)>>>|>,i>>|)>>|||w>|)>,i=2,\,n>>>> and <\eqnarray*> >>>||*|w>|)>O*D*>|)>O|)>.>>>> By Theorem, we may thus compute the relaxed product of >> and >> in time <\equation*> O>|\|>|)>*log>>>|)>|)>|)>O*log D|)>. We need to do |\|>> such relaxed multiplications. Now |\|>=O|)>> by Lemma, so the complete computation takes *|)>> operations in >. We finish this section with a bound for the size of reduced polynomials. <\proposition> Consider a monomial >*\*X>> with \1> for ,n>. If is reduced with respect to >>|)>\\>>, then <\eqnarray*> +1|)>*\*+1|)>>|>|*n!*.>>>> <\proof> Assume for contradiction that there exists an >*\*X>\*\|)>\\> with <\eqnarray*> +1|)>*\*+1|)>>|>|*n!*.>>>> Setting <\eqnarray*> >>|>|+1|)>*\*+1|)>|n>-1,>>>> our assumption can be rewritten as <\eqnarray*> >+1>|>||n>.>>>> Let \\> be such that <\eqnarray*> > \*M>||> \*M.>>>> For ,n>, Corollary implies <\equation*> *>+1|)>\w*+1|)>\2*>+1|)>.> Using Corollary and our assumption that \1>, this yields <\equation*> > B>\|n>|w>\+1|)>*|n>|>+1>\+1|2>\e>. This shows that >> divides . In combination with our assumption that > \*M=deg> \*M>, this means that \>>, a contradiction. One limitation of Proposition is that it does not apply to monomials >*\*X>> such that =0> for some index ,n|}>>. In this section, we show how to treat such lower dimensional \Pborder\Q monomials by adapting our reduction process. For any fixed subset ,\,X|}>>>, we will use the fact that the reduction process from the previous subsections can be applied to polynomials in the variables from and the ideal \\>. We next combine the reduction processes for all such subsets ,\,X|}>>. Given a finite subset ,n|}>>, we write <\eqnarray*> >|>|>*\*X>\\\i\S\e=0|}>>>|,\,X|]>>|>|\,\,X|]>\supp P\\|}>>>|>|>|\\,\,X|]>>>|>|>|S>X>.>>>> We note that > is an ideal of ,\,X|]>> with > \,\,X|]>/\\d>. Given \,\,X|]>>>, we define <\equation*> A>,n|}>\deg> P\0|}> to be the set of coordinates of . For any two subsets ,n|}>>, we define <\eqnarray*> T>|>|i\T\S,S\,i-1|}>=T\,i-1|}>|)>>>>> and note that this defines a total ordering on the set of subsets of ,n|}>>. A is a tuple \>\|}>|)>> and we call <\eqnarray*> >>|>|,n|}>\w\\|}>>>>> its set of coordinates. We say that > is if A>>w=1>>. For any monomial >*\*X>\\>>>, we define its >-degree by <\eqnarray*> > X>*\*X>>|>|A>>w*e.>>>> The >-degree induces an ordering on >>> by setting <\eqnarray*> >N>|>|> M\deg> N>>>> for all \>>>. We may naturally extend the notions of >-degree, leading monomials, to polynomials in ,\,X|]>>>>. We also define the >-simplest element of>>> to be the unique monic polynomial >\\>>> whose leading monomial is minimal for>>. Given a set > of generalized weights and ,n|}>>, we define <\eqnarray*> >|>|\\\A>=S|}>.>>>> If >> is non-empty, then we define <\eqnarray*> >N>|>|> M\deg> N|)>\> M=deg> N\M\N|)>>>|>>N>|>|*M\>\*N,>>>> for all \>. We next extend the definitions from section to the case when > is a set of generalized weights with \\> for every subset ,n|}>>. For each \\>, we take >> to be the >-simplest element of >>> and let <\eqnarray*> >>|>|>>>|)>.>>>> We will sometimes write ,\>> instead of >> when we need to emphasize the dependence on >. After declaring that \\>>, the set > can still be endowed with the lexicographical ordering. For increasing \\>, we now set <\eqnarray*> >>|>|L>*\>>\\>>*M\\>,A=A>|}>\\\>\>|)>.>>>> Sometimes, we will write ,\>> instead of >> when we need to emphasize the dependence on >. Finally, we define our total ordering >>> on > by <\eqnarray*> >>N>|>|\A=AM\>>>N|)>>>>> for all \>. <\proposition> The ordering >>> is quasi-admissible. <\proof> It is straightforward to check that >>> is indeed a total ordering such that <\eqnarray*> N>|>|>>N>>>> for all \>, by extending Lemma. Now consider \\> and <\equation*> M>\>>\,\,X|]>>>. Given supp B>\\>>>, Proposition implies <\eqnarray*> >>*N>|>>>>>|>>> If >|)>*N>=A=A>>, then this yields <\eqnarray*> >>*N>|>>>|>>> Otherwise, we have >|)>*N>\A=A>>, so >|)>*N>\A>, with the same conclusion. Given a general weight \>|)>> and a subset ,n|}>>> such that =1> for all E>, we define \>\|}>|)>> to be the generalized weight > with =w> if E> and =\> if E>. If > is admissible, then we note that > is again admissible. Given d>, we define <\eqnarray*> >|>|\\\\,E\,n|}>,i\E,w=1|)>|}>.>>>> Note that Lemma directly implies <\equation*> |\|>\2*|\|>\2* D+1|)>=O|)>.> The complexity bound from Theorem also still holds in our new setting: <\theorem> Let =\>. Given \,\,X|]>>, we may compute an extended quasi-reduction> using <\equation*> O*|)> operations in >. In addition, for all \\>, we have <\eqnarray*> > Q>*B>+1|)>>|>|*n!*.>>>> <\proof> For each \\>, we have <\equation*> >*supp Q>\\>\\,\>>>>. Using the same arguments as in the proof of Theorem, we obtain that the relaxed product >*B>> can be computed in time *log D|)>>. Since there are |\|>=O|)>> such products to be computed, the complexity bound follows. The inequality is also obtained in a similar way as for Theorem. This time, we have the following unconditional version of Proposition. <\proposition> Let >*\*X>> be a reduced monomial with respect to . Then <\eqnarray*> +1|)>*\*+1|)>>|>|*n!*.>>>> <\proof> The monomial is reduced with respect to if and only if is reduced with respect to >|)>\\>>>. By Proposition, this implies <\eqnarray*> +1|)>*\*+1|)>>|>|>*!*+1|)>,>>>> where \|\|>\n> and \dim> \,\,X|]>>/\>\d>. Let \|)>> be a tuple of pairwise distinct points and consider the problem of fast multi-point evaluation of a polynomial \,\,X|]>> at >. For simplicity of the exposition, it is convenient to restrict ourselves to the case when >> is a power of two (without loss of generality, we may reduce to this case by adding extra points). We define <\eqnarray*> >>|>|\,\,X|]>\P|)>=\|}>>>>> to be the vanishing ideal of >. We assume that we precomputed ,\>>|)>\\>>>. For any ,2-1>|}>> and ,d/m-1|}>>, we also assume that we precomputed ,\>>|)>\\>>>>, where =,\,\|)>\|)>> and =4*n!*>. We are now ready to state our main algorithm. <\specified-algorithm> <\description> \|)>> with >> and \,\,X|]>>. |)>>. We assume the precomputations that are stated above. <|specified-algorithm> <\enumerate> If =0>, then return the naive evaluation |)>>. Compute the quasi-reduction of ,\>>|)>\\>>>. Recursively apply the algorithm to > and . Recursively apply the algorithm to > and . Return the concatenations of the results of the recursive evaluations. <\theorem> Algorithm is correct and runs in time <\equation*> O*+*|)>. <\proof> The algorithm is clearly correct if =0>. For any recursive call of the algorithm with arguments \|)>> and >, Proposition ensures that we indeed have \,\,X|]>>>> with =4*n!*>. The correctness of the general case easily follows from this. As to the complexity bound, let us first assume that 4*n!*>. Then the same condition is satisfied for all recursive calls. Now the computation of takes <\equation*> O*|)>=O*|)> operations in >, by Theorem. Hence, the total execution time > satisfies <\eqnarray*> >|>||)>+O*|)>.>>>> By unrolling this recurrence inequality, it follows that =O*|)>>. If 4*n!*>>, then the computation of at the top-level requires *|)>> operations in > and we have just shown that the complexity of all recursive computations is *|)>>. <\render-proof|Proof of Theorem> The proof follows from Theorem and Proposition, by analyzing the cardinalities of the supports involved in the quasi-reductions. Let us revisit the quasi-reduction computed in step2 of Algorithm. From() in Theorem and() in Proposition, it follows that we may apply Proposition for =4*n!*>. For the recursive quasi-reductions, we may use even smaller values for >. This justifies that we may indeed take =O*log s|)>> in Theorem. <\bibliography|bib|tm-plain|> <\bib-list|29> A.BorodinR.T.Moenck. Fast modular transforms. Comput. System Sci.>, 8:366\U386, 1974. A.Bostan, G.LecerfÉ.Schost. Tellegen's principle into practice. , ISSAC '03, 37\U44. New York, NY, USA, 2003. ACM. D.G.CantorE.Kaltofen. On fast multiplication of polynomials over arbitrary algebras. , 28:693\U701, 1991. C.M.Fiduccia. Polynomial evaluation via the division algorithm: the fast Fourier transform revisited. , STOC '72, 88\U93. New York, NY, USA, 1972. ACM. D.HarveyJ.vander Hoeven. Faster polynomial multiplication over finite fields using cyclotomic coefficient rings. Complexity>, 54:101404, 2019. D.HarveyJ.vander Hoeven. Polynomial multiplication over finite fields in time >. , HAL, 2019. , accepted for publication in J.ACM. J.vander Hoeven. Relax, but don't be too lazy. Symbolic Comput.>, 34:479\U542, 2002. J.vander Hoeven. Faster Chinese remaindering. , HAL, 2016. . J.vander Hoeven. On the complexity of multivariate polynomial division. I.S.KotsireasE.Martínez-Moro, , 198, 447\U458. Cham, 2017. Springer International Publishing. J.vander Hoeven. . Scypress, 2020. J.vander HoevenG.Lecerf. On the bit-complexity of sparse polynomial multiplication. , 50:227\U254, 2013. J.vander HoevenG.Lecerf. Accelerated tower arithmetic. Complexity>, 55:101402, 2019. J.vander HoevenG.Lecerf. Fast multivariate multi-point evaluation revisited. Complexity>, 56:101405, 2020. J.vander HoevenG.Lecerf. Amortized bivariate multi-point evaluation. M.Mezzarobba, , ISSAC '21, 179\U185. New York, NY, USA, 2021. ACM. J.vander HoevenG.Lecerf. Fast amortized multi-point evaluation. Complexity>, 67:101574, 2021. J.vander HoevenG.Lecerf. On the complexity exponent of polynomial system solving. , 21:1\U57, 2021. J.HopcroftJ.Musinski. Duality applied to the complexity of matrix multiplication and other bilinear forms. , 2(3):159\U173, 1973. K.S.KedlayaC.Umans. Fast modular composition in any characteristic. , 146\U155. Los Alamitos, CA, USA, 2008. IEEE Computer Society. K.S.KedlayaC.Umans. Fast polynomial factorization and modular composition. Comput.>, 40(6):1767\U1802, 2011. D.Le BrigandJ.-J.Risler. Algorithme de Brill\UNoether et codes de Goppa. , 116(2):231\U253, 1988. F.Le GallF.Urrutia. Improved rectangular matrix multiplication using powers of the Coppersmith\UWinograd tensor. A.Czumaj, , 1029\U1046. Philadelphia, PA, USA, 2018. SIAM. R.T.MoenckA.Borodin. Fast modular transforms via division. , 90\U96. USA, 1972. IEEE. V.Neiger, J.RosenkildeG.Solomatov. Generic bivariate multi-point evaluation, interpolation and modular composition with precomputation. A.Mantzaflaris, , ISSAC '20, 388\U395. New York, NY, USA, 2020. ACM. M.NüskenM.Ziegler. Fast multipoint evaluation of bivariate polynomials. S.AlbersT.Radzik, , 3221, 544\U555. Springer Berlin Heidelberg, 2004. L.Robbiano. Term orderings on the polynomial ring. B.F.Caviness, '85. European Conference on Computer Algebra. Linz, Austria, April 1-3, 1985. Proceedings. Volume 2: Research Contributions>, 204, 513\U517. Springer-Verlag Berlin Heidelberg, 1985. D.S.Roche. What can (and can't) we do with sparse polynomials? C.Arreche, , ISSAC '18, 25\U30. New York, NY, USA, 2018. ACM. A.Schönhage. Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2. , 7:395\U398, 1977. A.SchönhageV.Strassen. Schnelle Multiplikation groÿer Zahlen. , 7:281\U292, 1971. <\initial> <\collection> <\attachments> <\collection> <\associate|bib-biblio> <\db-entry|+if2lDqI1qmMqAaI|inproceedings|CKL89> <|db-entry> E. Y. > <\db-entry|+2X2sGxMCqQBxuWk|inproceedings|BoLeSc:2003:tellegen> <|db-entry> G. É. > <\db-entry|+1LCfUIVm228oQhYU|inproceedings|GR11> <|db-entry> D. S. > <\associate|bib-bibliography> <\db-entry|+yAMRuva1eECsGs5|book|TeXmacs:vdH:book> <|db-entry> > <\db-entry|+Cwl6oOtBJq2Vc9|article|vdH:polexp> <|db-entry> G. > <\db-entry|+15oEgG3e1j4cwO00|article|LeBrigandRisler1988> <|db-entry> J.-J. > <\db-entry|+19vz8IGa1z6wBRzj|article|BM74> <|db-entry> R. T. > Comput. System Sci.> <\db-entry|+1xqpRSxg16lxOwfD|inproceedings|BostanLecerfSchost2003> <|db-entry> G. É. > <\db-entry|+1xqpRSxg16lxOwe2|inproceedings|Fiduccia1972> <|db-entry> > <\db-entry|+1Hcl3U922Lc9q60c|techreport|vdH:chinese> <|db-entry> > > <\db-entry|+1xqpRSxg16lxOweI|inproceedings|MoenckBorodin1972> <|db-entry> A. > <\db-entry|+jZzyy9fWllYOxa|article|CK91> <|db-entry> E. > <\db-entry|+cJSkMhbTYXNoYI|article|Sch77> <|db-entry> > <\db-entry|+VGDrIFx6jkaxhi|article|ScSt71> <|db-entry> V. > <\db-entry|+2EIRPFE3ONuyFfN|article|vdH:cyclomult> <|db-entry> J. van der > Complexity> <\db-entry|+2HvUs7XU1B9yIvnI|techreport|vdH:ffnlogn> <|db-entry> J. van der > >> , accepted for publication in J.ACM> <\db-entry|+2EIRPFE3ONuyFfG|article|vdH:tower> <|db-entry> G. > Complexity> <\db-entry|+17Sa78hcUEeG67|inproceedings|LeGallUrrutia2018> <|db-entry> F. > > <\db-entry|+17Sa78hcUEeG66|article|HopcroftMusinski1973> <|db-entry> J. > <\db-entry|+1GIl46OCkUAK86P|inproceedings|NuskenZiegler2004> <|db-entry> M. > T. > <\db-entry|+2dXiKvosB5WaTKW|inproceedings|KedlayaUmans2008> <|db-entry> C. > <\db-entry|+NuHCznHJqSBdAP|article|KedlayaUmans2011> <|db-entry> C. > Comput.> <\db-entry|+HCypi2vCoDaGyv|article|vdH:kucomp> <|db-entry> G. > Complexity> <\db-entry|+1NmkRag2bznaymZ|article|vdH:amp> <|db-entry> G. > Complexity> <\db-entry|+1GQhZkrScfYODlE|inproceedings|NeigerRosenkildeSolomatov2020> <|db-entry> J. G. > > <\db-entry|+2be1kgGa1yYJaxKK|inproceedings|vdH:biamp> <|db-entry> G. > > <\db-entry|+1xqpRSxg16lxOweD|inproceedings|vdH:sparsered> <|db-entry> > E. > <\db-entry|+5gyUr7A16TI54eY|inproceedings|Roche2018> <|db-entry> > > <\db-entry|+2DPRky2cs1xL3QZ|article|vdH:sparsemult> <|db-entry> G. > <\db-entry|+cJSkMhbTYXNoYJ|article|vdH:relax> <|db-entry> > Symbolic Comput.> <\db-entry|+2ZLjV7xS2U95RRiv|inproceedings|Robbiano1985> <|db-entry> > '85. European Conference on Computer Algebra. Linz, Austria, April 1-3, 1985. Proceedings. Volume 2: Research Contributions> > <\references> <\collection> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > <\auxiliary> <\collection> <\associate|bib> TeXmacs:vdH:book vdH:polexp LeBrigandRisler1988 BM74 BostanLecerfSchost2003 Fiduccia1972 vdH:chinese MoenckBorodin1972 CK91 Sch77 ScSt71 vdH:cyclomult vdH:ffnlogn vdH:tower vdH:tower LeGallUrrutia2018 HopcroftMusinski1973 NuskenZiegler2004 KedlayaUmans2008 KedlayaUmans2011 vdH:kucomp vdH:amp NeigerRosenkildeSolomatov2020 vdH:amp NeigerRosenkildeSolomatov2020 vdH:biamp NeigerRosenkildeSolomatov2020 vdH:amp vdH:sparsered vdH:sparsered vdH:amp vdH:sparsered Roche2018 vdH:sparsemult vdH:relax vdH:sparsered Robbiano1985 vdH:sparsered vdH:sparsered vdH:sparsered vdH:sparsered vdH:sparsered vdH:sparsered vdH:sparsered <\associate|toc> |math-font-series||font-shape||1.Introduction> |.>>>>|> |math-font-series||font-shape||2.Polynomial reduction> |.>>>>|> |2.1.Admissible orderings |.>>>>|> > |2.2.Sparse polynomial products |.>>>>|> > |2.3.Relaxed multivariate series |.>>>>|> > |2.4.Quasi-reduction |.>>>>|> > |2.5.Relaxed quasi-reduction |.>>>>|> > |math-font-series||font-shape||3.Heterogeneous orderings> |.>>>>|> |3.1.Weighted degree orderings |.>>>>|> > |3.2.Simplest elements of ideals |.>>>>|> > |3.3.Heterogeneous orderings |.>>>>|> > |3.4.Quasi-reduction |.>>>>|> > |math-font-series||font-shape||4.On the complexity of quasi-reduction> |.>>>>|> |4.1.Selecting the weights |.>>>>|> > |4.2.Complexity of quasi-reduction |.>>>>|> > |4.3.A degree bound for reduced polynomials |.>>>>|> > |math-font-series||font-shape||5.Reduction of the border> |.>>>>|> |5.1.Generalized weights |.>>>>|> > |5.2.Quasi-reduction for generalized weights |.>>>>|> > |5.3.Complexity analysis |.>>>>|> > |math-font-series||font-shape||6.Multi-point evaluation> |.>>>>|> |math-font-series||font-shape||Bibliography> |.>>>>|>