> <\body> |<\doc-note> Grégoire Lecerf has been supported by the French NODE project. Joris van der Hoeven has been supported by an ERC-2023-ADG grant for the ODELIX project (number 101142171). <\wide-tabular> ||||||| ||LOGO_ERC-FLAG_FP.png>|61.62pt|28.51pt||>>>>> ||<\author-affiliation> Laboratoire d'informatique de l'École polytechnique (LIX, UMR 7161) CNRS, École polytechnique, Institut Polytechnique de Paris Bâtiment Alan Turing, CS35003 1, rue Honoré d'Estienne d'Orves 91120 Palaiseau, France |>>||<\author-affiliation> Laboratoire d'informatique de l'École polytechnique (LIX, UMR 7161) CNRS, École polytechnique, Institut Polytechnique de Paris 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. We design slightly new faster deterministic algorithms to solve this problem for an algebraic computational model. For this purpose, we analyze the precomputation costs of recent amortized evaluation algorithms, and then study the complexity of the problem as a function of the number of evaluation points. |> 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 . The converse problem is called and takes a candidate support of as input. These problems naturally occur in several areas of applied algebra. For instance in, we have shown that fast multi-point evaluation leads to fast polynomial system solving. Multi-point evaluation with a large number of variables also leads to fast modular composition. The more specific bivariate case appears for example in the computation of generator matrices of algebraic geometry error correcting codes. The problem of multi-point evaluation is typically studied in the case when d>, where is the total degree of . One particularity of this paper is that, besides this classical case, we also study the complexity when and > have different orders of magnitude. Especially in the case when d>, our recent work on multipoint evaluation (when the set of points is fixed) turns out to be very useful; this application was also one of our motivations for the present work. In this paper, the number of variables is always assumed to be fixed, so the constants hidden in the \P\Q of our complexity bounds depend on. For complexity analyses, we will only consider algebraic complexity models like computation trees or RAM machines. The time complexity then measures the number of arithmetic operations and zerotests in>. The notation =>|)>> is a shorthand for =g*|)>>>>>; see25, section7> for technical details. The constant > will denote a real value between and such that two m> matrices over a commutative ring can be multiplied with >|)>> ring operations. The current best known bound is \2.371552>. The constant> will be a real value between 3 and4 such that the product of a m> matrix by a \m> matrix takes >|)>> operations; one may take \3.250385>. The first line of results, presented in section, concerns the derandomization of the Nüsken\UZiegler algorithm. When 3> our new deterministic bound coincides with their probabilistic one; see Theorem. For our deterministic evaluation in degree at |)>> points costs |)>> operations in >, whereas the probabilistic version of takes /2>|)>>, which tends to |)>> when > tends to the lower bound ; see Theorems and, and Remark. In section we turn to the amortized multi-point evaluation of multivariate polynomials. For such algorithms, the set of evaluation points is fixed, so we may use potentially expensive precomputations as a function of these points. A softly optimal algorithm for amortized multi-point evaluation was first given in. In section we provide a careful analysis of the cost of the precomputations. Building on algorithms from, it turns out that this can be done with a complexity exponent below the one of linear algebra: see Lemma. We next use this to derive our main complexity bounds for nonamortized multi-point evaluation: Theorems and. The latter theorem slightly improves upon the Nüsken\UZiegler algorithm when or 7>; see Remark for details. We also show that the evaluation at |)>/*+1|)>>|)>> points can be performed in softly linear time, which again improves upon the Nüsken\UZiegler algorithm. If , then Theorem also improves on our deterministic version of the Nüsken\UZiegler algorithm from Theorem; see Remark. The comparison with the randomized version is given in Remark. In order to design the above deterministic algorithms for any effective field>, we frequently need to assume that the cardinality of > is sufficiently large or that we explicitly know an element of a sufficiently large multiplicative order. This subtlety only concerns finite fields and is usually addressed by computing over an algebraic extension of >. Since we work over an arbitrary effective field in this paper, we need to deal with this extension issue in detail. In particular, we may not assume that the cardinality or characteristic of > are known. In Appendix, we present a general way to address these issues. Our solution can be implemented with programming languages that support generic programming, such as , , etc. The general problem of multivariate multi-point evaluation is notoriously hard. If =\>> or > is a field of finite characteristic, then theoretical algorithms due to Kedlaya and Umans achieve a complexity exponent >, where \0> is a constant that can be taken arbitrarily close to zero. Unfortunately, to our best knowledge, these algorithms do not seem suitable for practical purposes. Recent advances in this vein are to be found in. The best previously known complexity bound for and for general fields and input is due to Nüsken and Ziegler: the evaluation of at > P*deg> P|)>> points can be done using > P*> P|)>/2>|)>> operations in >, assuming suitable coordinates. So, for of total degree , the cost is an expected number of /2+1>|)>> operations in >, that equals |)>> without fast linear algebra, and that tends to |)>> when> tends to . We further mention for efficient algorithms for special sets of points>. Another recent result for any field >, and for , is due to Neiger, Salvy, Schost, and Villard. Their algorithm is derived from their fast modular composition algorithm. Given , , and in > of degree D>, they show how to compute the polynomial g rem h> by a probabilistic algorithm of Las Vegas type using an expected number of <\equation*> >|)>,\\1+-1>+-2>> operations in >; see 1.1>. Then the bivariate evaluation problem reduces to modular composition in the following way. First, up to a sufficiently generic linear change of the coordinates, their exist \\> of degree and \> of degree N> such that =|)>\\=0|}>>, so |)>> can easily be recovered from |)> rem \>. In10.3> it is shown that |)> rem \> can be computed using >|)>> operations in >, whenever |)>>, > has characteristic , and the input is sufficiently generic. Without fast linear algebra, that is when =3>, one has =5/3>>. With the best known value for>, one has \1.42945>. If > and > tend to their trivial lower bound and 3, then > tends to. In recent years, softly linear time has been achieved for multi-point evaluation and interpolation when > is a fixed generic tuple of points. These algorithms are in the sense that potentially expensive precomputations as a function of> are allowed. When the dimension is arbitrary but fixed, the amortized algorithms from generalize the classical univariate \Pdivide and conquer\Q approach, as presented for instance in10>. The results in restrict to the case >. They take into account the partial degrees of and are based on changes of polynomial bases that are similar to the ones of6.2>. The article handles arbitrary ( possibly non-generic) tuples of evaluation points>, while restricting to the amortized bivariate case and |)>>. New techniques for general dimensions were presented in. In the present paper we analyze the cost of the precomputations needed in. This is key for our improved complexity bounds for non-amortized multi-point evaluation, especially when is substantially smaller than >. Throughout this paper, we assume the dimension to be fixed. So the constants hidden in the O> of the complexity estimates will depend on. We recall that |)>> denotes the tuple of values |)>,\,P|)>|)>>. The >-vector space of the polynomials of total degreed> in > will be written d>>. The cardinality of > is written |\|>>. We denote by > the time that is needed to compute aproduct of two polynomials \> of degreed>. We make the usual assumptions that /d>> is nondecreasing as a function of and that =O|)>> whenever >. 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 even take =O> d>|)>>. A linear form \,\,x|]>> is said to the points > if it takes pairwise different values at pairwise different points of >. It will often be convenient to split > into non-empty subsequences,\,\>>. Then separating forms for each of the > with ,L> may be computed as follows. <\lemma> Let > be a set of |\|>|2>+\+|\|>|2>> elements in >. We can compute a joined separating form +\*x+\+\*x> for ,\,\> with ,\,\|)>>\\> using <\equation*> O|\|>+\+|\|>|)> operations in >. <\proof> Recall that > is constant. We proceed by induction on . If then the proof is immediate. Assume that 2> and let <\eqnarray*> :\>|>|>>|,\,x|)>>|>|,\,x|)>.>>>> By the induction hypothesis, we may compute ,\,\\\> in time |\|>+\+|\|>|)>>, such that x+\*x+\+\*x> is a joined separating form for |)>,\,\|)>>. Let <\equation*> \\|)>-x|)>|u|)>|)>-u|)>|)>>\1\i\L,|\,\|\>\\,\|)>\\|)>|}> with <\equation*> |\|>\|\|>|2>+\+|\|>|2>. Here |)>> stands for the first coordinate of >. If \\>, then +\*u> is a joined separating form for ,\,\>. We may compute |)>|)>> using |\|>+\+|\|>|)>> operations in > and then > using |\|>+\+|\|>|)>> further operations. We finally pick \\\\> and derive the required joined separating form +\*u> (so =\*\> for 3>) using =O> operations in >. If > is a separating form for >, then there exist a monic separable polynomial > of degree N> in |]>> and ,\,v> other polynomials in N>> such that <\equation*> \=,v|)>,\,v|)>|)>\\|)>=0|}>. If the points of the sequence > are pairwise distinct, it is well-known that these polynomials can be computed using *log N|)>> operations in>, thanks to sub-product tree algorithms; see10> or, for instance. Otherwise we will rely on the following lemma. <\lemma> The univariate representation of > can be computed using *log N|)>> operations in >. <\proof> We proceed recursively as follows. If then the univariate representation is obtained easily in time>. Otherwise, we let |N/2|\>> and we recursively compute the univariate representations >,v>,\,v>> of >=,\,\|)>> and >,v>,\,v>>> of >=,\,\|)>>>. We next compute \gcd>,\>|)>>, |\>>\\>/\>>, and >\v> rem |\>>>> for ,n>>. In this way, the univariate representation of > can be obtained as \\>*|\>>>>, and <\equation*> v\|\>>*>|)>*v>+|\>>*>|)>*>>|)>*U rem \ for ,n>, where is the inverse of > modulo >. The cost > of this method satisfies <\equation*> =++O*log N|)>, which yields =O*log N|)>>. > is a separating form> Let and be positive integer parameters such that d> and >. We expand the polynomial \,\,x|]>d>> to be evaluated as <\equation> P,\,x|)>=\l,\,i\l>P,\,i|)>>,\,x|)>*x>*\*x>, where > P,\,i|)>>\m> for \l,\,i\l> and 2>. We partition > into subsequences ,\,\> with |N/d|\>> and |\|>\d> for ,L>>. Let <\eqnarray*> :,l-1|}>>|>|,l-1|}>>>|:,m-1|}>>|>|,m-1|}>>>>> be arbitrary bijections, ,\,i|)>\i+i*l+\+i*l> and similarly for >. <\specified-algorithm> <\description> \,\,x|]>d>> and \|)>>. |)>>. > is a joined separating form for ,\,\>. <|specified-algorithm> <\enumerate> If d/2>> then set |d/L>|\>>. Otherwise set |d|\>>. Set |/m|\>>. For ,L>, compute the univariate representation |)>,v|)>,\,v|)>> of>. Note that \d> for all . For ,L> and =0,\,m-1>,, =0,\,m-1>, compute <\equation*> V,\,j|)>,k>\v>*\*v> rem \. We regard as a \L> matrix over |]>>, with entries of degreesd>. For ,L>, compute rem \,\,v rem \> and then <\equation*> v>*\*v> rem \, for =0,\,l-1>,, =0,\,l-1>. For =0,\,m-1>,, =0,\,m-1>, let ,\,i|)>,\,\,j|)>>|)>\\|]>> denote the coefficient ,\,i|)>,,\,j|)>>> of >*\*x>> in ,\,i|)>>\\|]>,\,x|]>>. We regard as a \m> matrix over |]>>, with entries of degrees d>. Compute <\equation*> W\Z*V. For ,L>, compute <\equation*> R\\l,\,i\l>W,\,i|)>,k>*v>*\*v> rem \. Return the concatenation of the vectors |)>|)>> for ,L>, where |)>> stands for the vector with the first coordinates of the points in >. <\proposition> Algorithm is correct and takes +N-2>*d>|)>> operations in > ifd/2>> and *-1|)>/2>|)>> operations otherwise. <\proof> The assumption on > is needed for step2. For all ,L> and all points ,\,a|)>> in > we verify in step6 that <\equation*> R|)>=\l,\,i\l>W,\,i|)>,k>|)>*a>*\*a>. In step5 we have <\eqnarray*> ,\,i|)>,k>|)>>||\m,\,j\m>Z,\,i|)>,\,\,j|)>>|)>*V,\,j|)>,k>|)>>>|||\m,\,j\m>P,\,i|)>,,\,j|)>>|)>*a>*\*a>>>|||,\,i|)>>,\,a|)>.>>>> From the expansion, we deduce that |)>=P,\,a|)>>. By Lemma, step2 takes > operations in>. Steps3 and4 take <\equation*> O*+l*|)>=+m|)>*N|)> operations. Step6 contributes *|)>=*N|)>> to the cost. Step7 performs univariate multi-point evaluations in total time *log N|)>>. For the complexity of step5 we distinguish the following cases: <\itemize> If d/2>>, then /2>|)>>, >|)>>, =O>, >|)>>, and >. Consequently, =O,m,L|)>|)>>, so the product can be split into products of \l> matrices, and the cost of step5 is <\eqnarray*> |l>*>*|)>>*|)>>||*l*-2|)>>*|)>>>||||L>*L-2>*|)>>>|||-2>*d|)>.>>>> In this case, the total cost of the algorithm is <\eqnarray*> +m|)>*N+L-2|)>>*d|)>>|||L>*N++1|)>-2|)>>*d|)>>>|||+N-2>*d>|)>.>>>> Otherwise, we have /2>\N>, m\d>, and /2>=O>. Consequently, =O,m,L|)>|)>>, the product can again be split into products of \l> matrices, and the cost of step5 becomes <\eqnarray*> |l>*>*|)>>*|)>>||*-1|)>>*|)>>>|||+1|)>*l*-1|)>>*|)>>>|||*-1|)>/2>|)>.>>>> This dominates the total cost of the algorithm since <\equation*> +l|)>*N|)>=/2>|)>. <\remark> The complexity of the product in step5 of Algorithm actually depends on the ratios of the dimensions of and . For simplicity, we have reduced this product to several products of \l> matrices, whence a complexity bound in terms of>. This choice is slightly sub-optimal if \2>; see. For instance, if |)>>, then |)>> and the product can be done faster, using only <\equation*> /2>|)>>*d|)>=*/2|)>+1>|)>. operations in >. The product Z*V> still dominates the total cost of Algorithm. <\remark> In their article, Nüsken and Ziegler present Algorithm in detail only for the case where and ; see8>. They give the complexity bound in terms of >, recalled in Remark, but also in terms of the partial degrees in > and>. The case where 3> is only mentioned in the conclusion of. In general, the form > does not necessarily separate all the > for ,L>. In such degenerate situations, one may apply a suitable change of coordinates before using Algorithm, provided that the cardinality of> is sufficiently large. In6>, Nüsken and Ziegler use a randomized method to compute such a change of coordinates. In this section, our first contribution is an alternative deterministic method, that takes advantage of the splitting of > into ,\,\>>. Another contribution is the complexity analysis in terms of the number of evaluation points. The following theorem summarizes the cost of our deterministic version of the Nüsken\UZiegler algorithm for 3>. <\theorem> Let 3> be a fixed dimension, let \,\,x|]>> be of total degree d>, let \|)>>, and let \log N/log|)>>, that is |)>>>. Then |)>> can be computed using |)>|)>>|)>> operations in >, where <\equation*> \|)>\if >\\>>|-2|)>*-|)>+1if >\\\+>>|+|)>*-1|2>if >+\\\1>>||)>*-1|2*\>if >1\\.>>>>> <\proof> Assume first that we are given ,d|)>+1> distinct elements in >. By Lemma, we may compute a joined separating form +\*x+\+\*x> for ,\,\>>using <\equation> O|)>=O+1|)>*d|)>=O|)>=O|)>+1/n|)>>|)> operations in >. Let <\eqnarray*> \>|>|>>|,\,x|)>>|>|+\*x+\+\*x,x,\,x|)>.>>>> We replace by A\P-*x+\+\*x|)>,x,\,x|)>>. This takes |)>> operations in > thanks toA, PropositionA.5> and the distinct elements in>. We next replace > by |)>:\\\|)>>, using > further operations. In this way, we reduce the problem to the case where > separates>. It remains to compute |)>> via Proposition. If \1/n>, that is d>, then the cost of Algorithm is |)>>. If \1/n> and d/2>>> then d> (since 3>) and the cost of Algorithm becomes <\equation*> +|)>-2|)>*\+1+|)>/n>|)>=|)>-2|)>*-1/n|)>+1>|)>. This dominates the contribution, since <\equation*> \+\+\-2|)>*-|)>+1. If d/2>> and d>, then the cost of Algorithm becomes <\equation*> *-1|)>/2>|)>=|)>+*-1|)>/2>|)>, which again dominates the contribution. Finally, if d> then the cost is <\equation*> *-1|)>/2>|)>=*-1|)>/|)>>|)>, still dominating the contribution. It remains to deal with the case where ,d|)>+1> distinct elements in > are not given. We appeal to Proposition: the hypotheses are met since the values returned by the present evaluation algorithm are independent of the ,d|)>+1> given elements of > or of an algebraic extension of it. The complexity overhead does not exceed, up to logarithmic factors. <\float|float|tbh> <\big-figure||gr-frame|>|gr-geometry||gr-grid||5>|gr-grid-old||5>|gr-edit-grid-aspect|||>|gr-edit-grid||5>|gr-edit-grid-old||5>|gr-grid-aspect|||>|gr-grid-aspect-props|||>|magnify|1|gr-snap||gr-dash-style|10|||||||>>||||>|||||>>|||>>|||>>|||>||>>|||>>||>|>|>||||>||>>||>>||>||>||>||2>--2|2*n>>|>|+1|2>--1|2*n>>|>|>|>|+>|>||)>>|>||>>>>> Complexity exponent |)>> for the evaluation in degree at *n>> points when 3>, via Theorem. Figure represents the complexity exponent |)>> introduced in Theorem. The bivariate case behaves differently from the general one, because the deterministic search of a separating form becomes the bottleneck. The following theorem summarizes the cost of our deterministic bivariate version of the Nüsken\UZiegler . <\theorem> Let \,x|]>> be of total degree d>, let \|)>>, and let \log N/log|)>>. Then |)>> can be computed using |)>>|)>>|)>> operations in >, where <\equation*> \>|)>\if >>\\>>|+if >>|\\\1|\>>>|>if >>1\\.>>>>> <\proof> Assume first that we are given +1> elements in >. By Lemma, a joined separating form +\*x> for ,\,\> can be obtained in time <\equation> O|)>=O|)>=O|)>+1/2|)>>|)>. Applying the linear change of coordinates to and > takes +N|)>> operations: here we may use1> to change the variables independently of the cardinality of >. If d>, then the cost of Algorithm is <\equation*> +N-2>*d>|)>=|)>-2|)>*-1/2|)>+1|)>>|)>, by Proposition. Since \3>, we also verify that <\equation*> max-2|)>*-1/2|)>+1|)>\max+1/2|)>. If d>, then the cost of Algorithm is -1|)>/2>|)>=>, which is again dominated by, up to logarithmic factors. Finally, if we are not given +1> elements in >, then we apply Proposition, as in the proof of Theorem. The next theorem rephrases the probabilistic version of Nüsken and Ziegler for two variables and when varies. <\theorem> Let \,x|]>> be of total degree d>, let \|)>>, let \log N/log|)>>, and assume that we are given > distinct elements in >. Then |)>> can be computed by a probabilistic algorithm of Las Vegas type using an expected number of |)>|)>>|)>> operations in>, where <\equation*> \|)>\if >>|\\1/2|\>>>|-2|)>*-|)>+1if >>|\\\|\>>>|+-1|4>if >>|\\\1|\>>>|-1|4*\>if >>|1\\|\>.>>>>> <\proof> In order to find a joined separating form +\*x> for ,\,\>, it suffices to take a random > in the given subset of >. The probability of success for each trial is1/2>>; see the proof of Lemma. So the expected number of trials is >>. The rest of the proof is adapted from the one of Theorem. Alternatively, one may adapt the proof of Theorem, by noting that the cost to compute a separating form is negligible, if we are allowed to use a randomized algorithm. <\float|float|tbh> <\big-figure||gr-frame|>|gr-geometry||gr-grid||5>|gr-grid-old||5>|gr-edit-grid-aspect|||>|gr-edit-grid||5>|gr-edit-grid-old||5>|gr-grid-aspect|||>|gr-grid-aspect-props|||>|gr-dash-style|10||>|||>>|||>>||>>||||>|>|>||>||>||||>>|||>>|+3|4>>|>||>>|+2|4>>|>|>|>|||>>|||)>>|>|>|)>>|>||>||>>||>||||>>||||>|>|>||>>|>|>>>> Deterministic and probabilistic complexity exponents for bivariate evaluation in degree at >> points, via Theorems and. Figure displays the complexity exponents introduced in Theorem and Theorem. Note that >=\> when =3>. In this section, we refine our complexity analysis of the amortized algorithm for the evaluation of multivariate polynomials from. The main novelty is a precise analysis of the cost of the required precomputations. From this, we will be able to derive new complexity bounds for non-amortized multi-point evaluation. Throughout this section \,\,x|]>> and \|)>> denote the polynomial and the tuple of evaluation points, respectively. We also write for the ideal of ,\,x|]>> that consists of all polynomials that vanish at >. We recall that the dimension is fixed. Let us consider a vector <\equation*> \\,\,s|)>\\, called a for the degrees, the >-degree of a row vector =,\,a|)>> in > is defined as <\equation*> deg> \\max +s,\,deg a+s|)>. If > is non-zero, then the of > is the largest index for which the latter is reached. The entry > is called the , and its degree is the . If > is zero, then its pivot index is defined to be zero. Let denote a n> matrix with entries in >. The matrix is in >-Popov form> if the following properties are satisfied: <\itemize> The positive pivot indices of the rows of are in increasing order; The pivots of the rows of are monic ( have leading coefficient ); The pivots of have a degree strictly larger than the other elements in their column. If and is non-singular, then its pivots are the diagonal elements. In this case, satisfies the \Ppredictable degree\Q property: <\lemma> Let be a non-singular n> matrix in Popov form. If =,\,b|)>\\*M> forsome row vector \\>, then <\equation*> deg> \=max,n>+deg a|)>, where > denotes the >-degree of the -th row of . <\proof> See1.1>, for instance. Given non-constant polynomials ,\,\> in >, and given a L> matrix with entries > in deg \>>, Popov forms will be used to compute the kernel of the map <\eqnarray*> \>|>|,L>\/|)>>>||)>,r>>|>|,r>F*u|)>,L>.>>>> Since the vectors ,0,\,0|)>>, ,0,\,0|)>>,, ,0,\|)>> are a free family in , the kernel of is a free >-module of rank . <\proposition> 1.4> Given non-constant polynomials ,\,\> in > and anL> matrix with entries > in deg \>>, there exists a unique r> matrix in Popov form such that the rows of are a basis of ker . If then can be computed using -1>*N|)>> operations in >, where deg \+\+deg \>. Let > be the set of monomials >*\*x>> with ,\,e\\>. Any polynomial \,\,x|]>>> can uniquely be written as a linear combination <\equation*> P=\>P*M with coefficients > in > and finite support <\equation*> supp P\\\P\0|}>. Given a total ordering> on>, the support of any non-zero polynomial admits aunique maximal element >\\> that is called the of ; the corresponding coefficient >=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>>|>|\f>|>>|=f\e\f>|>>|>|>|=f\\\e=f\e\f>|>>>>>>>> is admissible. In the rest of the paper, an will be a -tuple <\equation*> \=,\,w|)>\\i\\|}>> with <\equation> w*\*w=1. Given amonomial >*\*x>>, we define its >-degree> by <\equation*> deg>>*\*x>|)>\w*e+\+w*e. For a non-zero polynomial \>P*M\\,\,x|]>>, we define its >-degree> by <\equation*> deg> P\max\> > 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. 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>>. From1>, we know that <\equation> deg> B>\|n>|w>, for ,n>. The main aim of this section is an efficient algorithm for the computation of>>. For this purpose, we may assume without loss of generality that we ordered the coordinates such that \\\w>. By(), this yields \1\w*\*w>. Using also, we get <\equation*> i\n>deg> B>\*\*w>*i\n>|n>\|)>/n>. It follows that the set <\equation*> \\>*\*x>\0\e\|n>|w>,i=2,\,n|}> of monomials in ,\,x> has cardinality <\equation> r\2*|)>/n>=O/n>|)>. We sort the monomials of > according to the ordering >> for which <\equation*> x>*\*x>\>x>*\*x> if and only if <\equation*> x>*\*x>\x>*\*x>, where <\eqnarray*> >|>|>|>|>|**e+\+w*e-*f+\+w*f|)>|)>.>>>> For this choice of > and >, we note that <\equation*> w*e+\+w*e=w*f+\+w*f. Let <\equation*> b\>b\>\\>b denote the monomials of > in increasing order. As in the previous sections, the sequence of points > will be split into subsequences ,\,\> of cardinality M> such that N> and >. More precisely, until section, we take <\equation> M\|N|\>L\|N/M|\>, so that /n>|)>>. <\lemma> Let and be as in> and assume that ,\,x> are joined separating forms for ,\,\>. Then we can compute >> using <\equation*> -1|)>*/n>|)> operations in >. <\proof> Without loss of generality, we may order the coordinates such that \\\w>, after which we may use the above notation. We write |]>,\,x|]>>> for the set of polynomials over |]>> with support in>. Let be the Popov form of the matrix representing the kernel of the projection <\eqnarray*> \|]>,\,x|]>>>|>|,\,x|]>/I>>||>|>>> in the basis ,\,b> and for the shift vector <\equation*> \\,\,s|)>, where \w*deg>|)>\\>. Regarding >> also as a |]>>-vector in |]>,\,x|]>>>, wehave <\equation> deg> B>=w*deg> B>. Since |]>> is principal, is a free |]>>-module. Let |)>> be the minimal polynomial of> in . Since |)>*b,\,\|)>*b> is a free family of , the rank of is. Consequently, is a non-singular r> matrix. Every row > of with ,r >can also be regarded as a polynomial in |]>,\,x|]>>>>, which belongs to . We have <\equation> deg> U=w*deg> U. By construction, there exist ,\,a> in |]>> such that <\equation*> B>=a*U+\+a*U. By Lemma, , and, we have <\equation*> deg> B>=max,r>> U+w*deg a|)>. Let > be the set of row indices such that > U> is minimal, that is <\equation*> \\,r|}>\deg> U=min,r> deg> U|}>. By the minimality of >> and since the > belong to , the polynomials > with \> must be zero and the others must be in >. Consequently, >=\>a*U>. By definition (see section), the pivot index of <\equation*> U,\,x|)>=j\r>U|)>*b is . This means that <\equation*> deg> U,\,x|)>=deg>|)>*b|)> and <\equation*> deg>|)>*b|)>\deg>|)>*b|)> for all i>. If i> is such that >|)>*b|)>=deg>|)>*b|)>>, then the definition of the ordering>> ensures that \x>*b>, where \w*> b-deg> b|)>>. It follows that =deg U|)>-deg U|)>>, whence |)>>*b\>x|)>>*b>. In other words, the leading monomial of > for >> is the leading monomial of |)>*b>. Consequently, the leading monomial of >> is the leading monomial of *b>, where max\\a\0|}>>. Finally, the minimality of>> implies that >> is >-proportional to >>. In order to obtain the Popup form , we first compute the univariate representations of> for ,L>: this takes > operations in > by Lemma. The univariate representation of > is given by a monic polynomial \\|]>>> of degree |\|>\M> and polynomials ,\,v\\|]>> of degrees M>. Now consider the matrix \|]>L>> defined by <\equation*> F\b,\,v|)> mod \ for ,r>> and ,L>: the entries > can be computed in softly linear time =>. Since and imply >, we may apply Proposition. We conclude that can be computed using <\equation*> -1>*N|)>=/n>|)>-1>*N|)>=-1|)>*/n>|)>. operations in >. Given N>, we define <\equation*> \\>,\,2>|)>\,\,e|)>\\,e+\+e=0,2|\|>>\D,\,2|\|>>\D|}>. Given a finite subset ,n|}>>, we write \1> if S> and \0> otherwise. We introduce <\eqnarray*> :\>|>|>>|,\,x|)>>|>|*x,\,\*x|)>.>>>> We denote by > the image of > under > and we define <\eqnarray*> >|>|>*\*x>\\\i\S\e=0|}>>>|,\,x|]>>|>|\,\,x|]>\supp P\\|}>>>|>|>|\,\,x|]>.>>>> Given a general weight \>|)>> and a subset ,n|}>>> such that =1> for all E>, we define \>\|}>|)>> to be the weight > with =w> if E> and =\> if E>. If > is admissible, then we note that > is again admissible for ,\,x|]>> where ,n|}>\ E>. We further let <\eqnarray*> >|>|\\\\,E\,n|}>,i\E,w=1|)>|}>.>>>> The family of simplest polynomials >|)>\\>>> is called an for > and. <\lemma> Let and be as in and assume that ,\,x> are joined separating forms for ,\,\>. Then a heterogenous basis >|)>\\>> can be computed using <\equation*> -1|)>*/n>*log D|)> operations in >. <\proof> The cost for computing a single >> is given in Lemma. On the other hand, we have \2*card \>>, and =O D|)>> by2>. Let and are still as in. Assume that is a power >>. A for> and consists of the followingdata: <\itemize> a heterogenous basis for > and , for all ,2-1>> and ,N/m-1>, a heterogeneous basis for \,\,\|)>\|)>> and \4*n!*>. We say that linearly independent linear forms ,\,u> > if each of them is a joined separating form for ,\,\>. We say that they > if they weakly separate each of the above > for ,2-1>> and ,N/m-1>. \ In order to construct recursive heterogeneous bases, we need coordinates ,\,x> that recursively weakly separate >. This is the purpose of the following lemma. <\lemma> Assume that we are given +1|)>*N+1> points in >. A basis ,\,u> of linear forms that recursively weakly separate > can be computed using |)>> operations in >. <\proof> With and as in we have <\equation> L*\+1|)>*=**\*|)>*N\N. Let us call ,\,\> the standard split of >. We construct the sequence of sequences of points > that consists of the standard split of> and the standard splits of > for ,2-1>> and ,N/m-1>. Let \|m|\>>. The standard split of > consists of \|m/M|\>> sequences of cardinality M>. The total number of points in > is at most +1|)>*N=O>. Using, we verify that <\eqnarray*> \\>|\|>|2>>|>|+,2-1>>i\N/m>L*|2>>>||>|+\**m>>||>|+1|)>*N.>>>> By Lemma, we may compute a joined separating form =x+\*x+\+\*x> for>, in time +1|)>*N|)>=|)>>, using the given subset of >. For ,n>, we take \x+\*u> for some > in > such that <\equation*> \\--x|u-u> for all distinct points \> in >, for all > in >. Since > must be different from +1|)>*N>> elements in >, a suitable > can be found in the given subset of >. In this way, > is a joined separating form for >. By construction, ,\,u> are >-linearly independent. The evaluation of > at all points \> in> takes > operations in >. For each ,n>, the set of unsuitable values for > can be computed using *log N|)>> operations in >. <\lemma> Assume that ,\,x> recursively weakly separate >. Then a recursive heterogeneous basis for > and N> can be computed using <\equation*> -1|)>*/n>*log D|)> operations in >. <\proof> This is a direct consequence of Lemma; recall that is fixed. We gather the preceding results of this section into the following statement. <\lemma> Let \> and >. Assume that D> is a power >>, and that we are given and element of order <\equation*> \max+1|)>*N+1,d+1,4*n!*|)> in >. Then we can compute an invertible n> matrix over > such that ,\,x> recursively weakly separate |)>>, together with a recursive heterogeneous basis for |)>> and , using <\equation*> -1|)>*/n>*log d|)> operations in >. Having computed such a basis, any polynomial of total degree d> can be evaluated at > using > operations in>. <\proof> The case is well-known; see10>. So let us assume 2>. The computation of and of the recursive heterogeneous basis has been addressed in Lemmas (using the element of order +1|)>*N>) and. Given and , the computation of the polynomial U> takes|)>> operations in> thanks toA, PropositionA.5> and the element of orderd>. By5>, U> can be evaluated at |)>> using |)>> operations in >. Here > is a cost function for multiplying two sparse polynomials and in ,\,x|]>>>, where is the maximum of the sizes of the supports of , , and . As detailed in the proof of1>, we may take =>, thanks to the element of order4*n!*>>. <\theorem> Let 1> be a fixed dimension, let \|)>> and \> be such that |)>>. After the precomputation of suitable data, as a function of > and only, any polynomial of total degree d> can be evaluated at > using <\equation*> |)> operations in >. Moreover, the precomputation can be done using <\equation*> -1|)>*/n>|)>*> operations in >. <\proof> Let >. We first handle the case where D>. In this way, up to repeating some points in >, we may assume that is a power of two such that D>. If we are given an element of order max+1|)>*N+1,d+1,4*n!*|)>>, then the complexity bounds follow from Lemma. Otherwise, we may appeal to Proposition to ensure the existence of this element of high order. In this way, note that the precomputed data are in general defined over an extension of the form /|)>>, and that must then be evaluated over this extension, following the rules described in the proof of Proposition. Finally, if D> then we subdivide > into =O> subsequences of size|D/2|\>>>, and then repeat the precomputations and the evaluations for each subsequence. Using the preceding amortized evaluation strategy, we analyze the cost of a single multi-point evaluation in variables as a function of . <\theorem> Let 1> be a fixed dimension. A polynomial \,\,x|]>> of total degree d> can be evaluated at |)>>> points in> using |)>|)>>|)>> operations in >, where <\equation*> \|)>\if >>|\\*\+1>|\>>>|+1-*\+1>if >>|*\+1>\\\1|\>>>|*\+1>|)>*>if >>|1\\|\>.>>>>> <\proof> We start with the case \1>. We subdivide > into subsequences ,\,\> of cardinality M>, where N> and >. The evaluations of at > for ,L>> take <\equation> +M-1|)>*/n>|)>*L|)>=+M*\+1|)>/n>|)>*L|)> operations in > by Theorem. We distinguish the following cases: <\itemize> If *\+1|)>/n>\d>, then we set N> and 1>, so the cost is at most |)>>. Otherwise we take <\equation*> M\|d|*\+1>>|\> and |N/M|\>>, so the cost simplifies into <\equation*> *+1|)>|)>=|*\+1>>+d|)>=|*\+1>>|)>. Finally, if d> then we subdivide > into |)>> subsequences of size d>, so the evaluation cost becomes <\equation*> |)>>*N/d|)>=-1|)>/\>|)>. <\remark> If and \3>, then Theorem always improves on Theorem. <\remark> We have plotted the complexity exponent |)>> for bivariate multi-point evaluation in Figure.<\float|float|tbh> <\big-figure||gr-frame|>|gr-geometry||gr-snap||magnify|1|gr-transformation||||>|gr-grid||2>|gr-grid-old||2>|gr-edit-grid-aspect|||>|gr-edit-grid||2>|gr-edit-grid-old||2>|gr-grid-aspect||>|gr-grid-aspect-props|||>|gr-dash-style|10|||>>|||>|+1>>|>|>||>|||>>|>|>|||>>||||>|||>>||>|||>||>>|+1>>|>|||>>|||>>||>>||>||)>>|>||)>|>>>> Complexity exponent |)>> for bivariate evaluation in degree at >> points via Theorem. For comparison, we also show the complexity exponent |)>> from Theorem. Comparing with Theorem, while assuming that \3>, we observe that <\itemize> |)>=\|)>> if \1/2>, |)>\\|)>> if \\\>, |)>\\|)>> if \\>, where \+2|2*+1|)>>\.> <\remark> Comparing with Theorem, the complexity exponents > and > tend to +1|)>/2> and > respectively, when tends to infinity. If \2>, then our new bound improves on the Nüsken\UZiegler algorithm for large . More precisely, we have <\equation*> \-\=-1|)>*-2|)>*n+1-\|)>*|2*n**\+1|)>>, so our method is faster when <\equation*> n\-1|\-2>. As in section, let us now analyze the variant when we apply the amortized evaluation method for variables to the non-amortized problem for variables. <\theorem> Let 3> be a fixed dimension. A polynomial \,\,x|]>> of total degreed> can be evaluated at |)>>> points in> using |)>|)>>|)>> operations in >, where <\equation*> \|)>\if >>|\\*\+1>|\>>>|+-1|)>*|*\+1>if >>|*\+1>\\\1|\>>>|-1|)>*|*\+1>*>if >>|1\\|\>.>>>>> <\proof> Again, we subdivide > into subsequences ,\,\> of cardinality M> such that |)>>. We expand as a polynomial in >, <\equation*> P,\,x|)>=i\d>P,\,x|)>*x, and let :\\\> denote the projection ,\,x|)>\,\,x|)>>. We apply Theorem successively with |)>,\,\|)>> in the role of >. The total cost of the precomputations is <\equation*> -1|)>*/>|)>*>, after which the cost of the evaluations of ,\,P> at |)>> becomes <\equation*> |)>. We deduce |)>> in time >. Now we set <\equation*> |M\||)>-1|)>*/|)>>|\>|\>|L\|N/M|\>|\>. Using 3>, we verify that |)>>. In total, the computation of |)>> costs <\eqnarray*> ||-1|)>*/>+d|)>+d*N|)>>>|||+d*N|)>>>|||*d+d*N|)>>>|||-1|)>*/|)>>+d+d*N|)>>>|||-1|)>*/*\+1|)>>+d+d*N|)>.>>>> Still using 3>, we note that <\equation*> -1|)>*|*\+1>-1=**\-n+1|)>|*\+1>\0. Consequently, the total cost simplifies to -1|)>*/*\+1|)>>+d|)>>. <\remark> Since the map *\+1>> is decreasing for 1>, we have <\equation*> *\+1>\*\+1>. If *\+1>\\\1>, then <\eqnarray*> |)>-\|)>>||-1|*\+1|)>**\+1|)>>\0.>>>> Consequently, if 3>, then Theorem always improves upon Theorem. <\remark> The function |)>> from Theorem is plotted in Figure.|gr-frame|>|gr-geometry||gr-grid||5>|gr-grid-old||5>|gr-edit-grid-aspect|||>|gr-edit-grid||5>|gr-edit-grid-old||5>|gr-grid-aspect|||>|gr-grid-aspect-props|||>|gr-snap|||>|||>>||+1|3>>|>||>|||>>|>|>|||||>>|>|>||>>|||+2|3>>|>|+1>>>|>>||>>|||>>||>||>|>|>||>>||>>|||>>||>|||>>||)>>|>||)>>|>|||>>||||>||>||>>|+1>>>|>>|>>> Complexity exponent |)>> for the evaluation of a polynomial in three variables of degree at >> points via Theorem. > In comparison with Theorem, we note that =\> at the limit when =2>. However, for the best currently known upper bound for >, we have |)>\\|)>>> for all \1/3>, even when taking into account Remark. More precisely, for \2.371552>, we have \1.406801>. At the same time, for \>>, the exponent of the Nüsken\UZiegler algorithm is +1|)>/3\>. <\remark> For =1>, it is instructive to compare Theorem with the best Nüsken\UZiegler style complexity bound */2|)>+1>|)>> of Remark: <\itemize> If =3> and =4>, then the bound from Theorem is always better. For the best currently known values \>> and \3.250385>>, we verify numerically that <\equation*> 1+-1|)>*|*\+1>=\\*/2|)>+1|n> if and only if or 7>. At the limit when =2> and =3>, we have =\=> and \\> for3>>. Let > be an effective field, and let >\\\> denote its multiplicative group. We are interested in finding elements of >> of a sufficiently high order, possibly after replacing> by a suitable extension. The following algorithm finds such elements whenever the cardinality of > is sufficiently large. <\specified-algorithm> <\description> A subset > of >> of cardinality 1>. An element of >> of order N>. <|specified-algorithm> <\enumerate> Set 1>, 1>, and \|log N|\>>. For each element in > do: <\enumerate> If =1> then continue the loop of step2 with the next element in >. Compute > for ,N-1>. If the order of is N>, then return . Compute gcd>, \gcd>|)>>, \m/gcd>|)>>, \a>>, and\g>>. Compute the integers and of the Bézout relation +v*>. Replace by*> and by *>. If N> then return . <\proposition> Algorithm is correct and performs > operations in >. <\proof> Let > denote the current subset of the elements of > that have been handled when entering step2.a. We will show by induction that the elements of > have order dividing, and that has order . Of course, these properties hold at the beginning, when > is empty. If =1> then the induction hypothesis is preserved. If the algorithm exits at step2.c, then the output is clearly correct. Otherwise, the order N-1> of can be read off from the computations of step2.b. Let ,\,p> be the prime numbers occurring in the factorization of , of respective multiplicities ,\,e> in and ,\,m> in , so we have <\equation*> e=p>*\*p>m=p>*\*p>. Some of the > or > may be zero here. Since and are at most , the > and > are at most >. From <\equation*> d=gcd=i\s>p,m|)>>, and since does not divide , we note that the integer <\equation*> e/d=i\s>p-min,m|)>> is at least 2> and only divisible by the primes > such that \m>. It follows that <\equation*> =i\s>>|\m>>>>>>p>,gcd>|)>=i\s>>|\m>>>>>>p>,=i\s>>|\m>>>>>>p>, hence > and > are coprime and <\equation*> *=m*i\s>>|\m>>>>>>p-m>\2*m. Now > has order > and > has order >, whence *|)>*>=1>. If is a prime divisor of >, then <\equation*> *|)>*|)>/p>=*/p|)>>=|)>*/p|)>>=/p|)>>\1. Similarly, if is a prime divisor of >, then *|)>*|)>/p>\1>. Consequently, *> has order*>. In particular, if the algorithm exits in step2.f, then the output is correct. From <\equation*> *=m*i\s>>|\m>>>>>>p-m>=i\s>>|\m>>>>>>p>*i\s>>|\m>>>>>>p> we note that and divide *>. Therefore the induction hypothesis again holds at the end of step2. Since the orders of the elements of > divide , they are roots of the polynomial -1>, whence |\|>\m>. This shows that the algorithm works as expected. Steps2.a, 2.d, and 2.e take > operations in >. Step2.b takes > operations. In step2.e, the integer is at least doubled, so step2.b can occur only > times. Overall, the total cost is >. We finally observe that the gcds and the Bézout relations can be computed using a negligible number of |)>> bit operations. In order to be painstakingly precise, we note that such bit operations can be emulated by operations over > in our algebraic complexity model. In many usual cases, it is known that Algorithm is suboptimal. In particular, if the characteristic of > is zero, then has always order N>. If =\> is a finite field, then >> is cyclic and primitive elements can be obtained more efficiently; see for instance, but also the survey. As an advantage, Algorithm is field agnostic. This property seems mostly of theoretical interest, but it turns out to be useful when programming generic algorithms, that do not require specific properties of >: for instance the characteristic or the cardinality of > are not computable. The following proposition explains how to use Algorithm even without any piece of information about >. <\proposition> Let be a computation tree of total cost over >, such that <\itemize> One of the input values of must contain an element > of order N>; The output values of are independent of the value taken for >, even when > is taken in an algebraic extension > of > and when is evaluated over >.\ Then there exists a computation tree > of total cost <\equation*> O*log log N+N*log N|)> that computes the same as but without requiring an input element of order N.> <\proof> We are interested in computing an element of order N>. First, we can compute the sequence of integers ,N> in > using > additions, and then determine whether > is N> or not. If \N>, then we can use Algorithm in order to obtain an element > of > of order N>. In this case, > simply runs with >. Otherwise, char \\N>. We shall compute in a sufficiently large algebraic extension of > as follows. Let |log/log p|\>> be the first integer such that <\equation*> p-1\N. Thanks to3.2>, we may deterministically construct a monic irreducible polynomial \\> of degree in > using |)>*e>=O> operations in>. In this way, /|)>> is the finite field with > elements. We can enumerate nonzero elements of /|)>> and then use Algorithm in order to obtain an element> of /|)>> of order N>. We regard > as a polynomial in > of degreee>. Now we regard as a computation tree over /|)>>, using > in place of the input element of order N>. While executing for given input in >, sums and products can be lifted straightforwardly to /|)>>: elements of /|)>> are represented by polynomials of degreee>. When testing whether an element <\equation*> a\\/|)> is invertible or not, we proceed as follows: <\itemize> If > is identically zero, then the test returns false. If > is invertible modulo >, then the test returns true. Otherwise, > can be factored =\*\>, with \gcd,a|)>>, \1>, and \1>. We continue our computations with > in the role of >, while projecting all previously computed results from /|)>> in /|)>>. In particular, > becomes identically zero after this projection, and the test returns false. Note that > remains embedded in /|)>> whenever > is replaced by any nontrivial factor over >. In particular, the order of > remains N> after any such replacement. At the end, we thus obtain the evaluation of over />|)>>, where >> is anon-constant factor of the original >. This proves the correctness of our method. Computing > takes > operations thanks to Proposition. The evaluation of over /|)>> requires ring operations or extended gcd computations for polynomials over > of degree at most . This contributes*log e|)>=O*log log N|)>> to the cost. The overall cost is therefore as claimed. <\bibliography|bib|tm-plain|> <\bib-list|30> S.Abelard, A.CouvreurG.Lecerf. Efficient computation of Riemann\URoch spaces for plane curves with ordinary singularities. , 35(6):739\U804, 2024. V.Bhargava, S.Ghosh, Z.Guo, M.KumarC.Umans. Fast multivariate multipoint evaluation over all finite fields. , 221\U232. New York, NY, USA., 2022. IEEE. V.Bhargava, S.Ghosh, M.KumarC.K.Mohapatra. Fast, algebraic multivariate multipoint evaluation in small characteristic and applications. , 2023. Article42. A.Bostan, G.LecerfÉ.Schost. Tellegen's principle into practice. , ISSAC '03, 37\U44. New York, NY, USA, 2003. ACM. P.Bürgisser, M.ClausenM.A.Shokrollahi. , 315. Springer-Verlag, 1997. D.G.CantorE.Kaltofen. On fast multiplication of polynomials over arbitrary algebras. , 28:693\U701, 1991. Q.Cheng. On the construction of finite field elements of large order. , 11(3):358\U366, 2005. S.Gao. Elements of provable high orders in finite fields. , 127(6):1615\U1623, 1999. J.vonzur GathenJ.Gerhard. . Cambridge University Press, New York, 3rd, 2013. D.HarveyJ.vander Hoeven. Faster polynomial multiplication over finite fields using cyclotomic coefficient rings. Complexity>, 54:101404, 2019. J.vander Hoeven. . Scypress, 2020. J.vander HoevenR.Larrieu. Fast reduction of bivariate polynomials with respect to sufficiently regular Gröbner bases. C.Arreche, , ISSAC '18, 199\U206. New York, NY, USA, 2018. ACM. 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.vander HoevenG.Lecerf. Amortized multi-point evaluation of multivariate polynomials. Complexity>, 74:101693, 2022. J.vander Hoeven, G.Lecerf, B.Mourrain etal. Mathemagix. 2002. . J.vander HoevenÉ.Schost. Multi-point evaluation in higher dimensions. , 24(1):37\U52, 2013. 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. V.Neiger. . , École Normale Supérieure de Lyon (France) \U University of Waterloo (Canada), 2016. . V.Neiger. Fast computation of shifted Popov forms of polynomial matrices via systems of modular polynomial equations. , ISSAC '16, 365\U372. New York, NY, USA, 2016. ACM. 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. V.Neiger, B.Salvy, É.SchostG.Villard. Faster modular composition. ACM>, 71(2):1\U79, 2023. Article No.11. M.NüskenM.Ziegler. Fast multipoint evaluation of bivariate polynomials. S.AlbersT.Radzik, , 3221, 544\U555. Springer Berlin Heidelberg, 2004. V.Shoup. New algorithms for finding irreducible polynomials over finite fields. , 54(189):435\U447, 1990. V.Shoup. Searching for primitive roots in finite fields. , 58:369\U380, 1992. I.Shparlinski. On finding primitive roots in finite fields. , 157(2):273\U275, 1996. V.V.Williams, Y.Xu, Z.XuR.Zhou. New bounds for matrix multiplication: from alpha to omega. D.P.Woodruff, , 3792\U3835. Philadelphia, PA 19104 USA, 2024. SIAM. <\initial> <\collection> <\attachments> <\collection> <\associate|bib-bibliography> <\db-entry|+1PlYSeg92FURz2kB|book|TeXmacs:vdH:book> <|db-entry> > <\db-entry|+Cwl6oOtBJq2Vc9|article|vdH:polexp> <|db-entry> G. > <\db-entry|+NuHCznHJqSBdAP|article|KedlayaUmans2011> <|db-entry> C. > Comput.> <\db-entry|+15oEgG3e1j4cwO00|article|LeBrigandRisler1988> <|db-entry> J.-J. > <\db-entry|+2be1kgGa1yYJaxKK|inproceedings|vdH:biamp> <|db-entry> G. > > <\db-entry|+19qSWaJJnkT|article|vdH:genamp> <|db-entry> G. > Complexity> <\db-entry|+2MBfjYgs1WYemMtm|book|BuClSh1997> <|db-entry> M. M. A. > <\db-entry|+2WheVMn2twB3YIJ|book|GathenGerhard2013> <|db-entry> J. > <\db-entry|+2txxTg5dpQ5|inproceedings|WilliamsXuXuZhou2024> <|db-entry> Y. Z. R. > > <\db-entry|+1GIl46OCkUAK86P|inproceedings|NuskenZiegler2004> <|db-entry> M. > T. > <\db-entry|+27PHx1kC20iqo7p|inproceedings|Neiger2016> <|db-entry> > <\db-entry|+qYhUkmR1lNMNvFz|misc|vdH:mmx> <|db-entry> G. B. > > <\db-entry|+HCypi2vCoDaGyv|article|vdH:kucomp> <|db-entry> G. > Complexity> <\db-entry|+1HaN8hLm1SNDYO5Q|inproceedings|BhargavaGhoshGuoKumarUmans2022> <|db-entry> S. Z. M. C. > <\db-entry|+1HaN8hLm1SNDYO5R|article|BhargavaGhoshKumarMohapatra2023> <|db-entry> S. M. C. K. > 42> <\db-entry|+C2mCMTwEO5guWF|article|vdH:mmeval> <|db-entry> É. > <\db-entry|+1AmLVKAfE2Q|article|NeigerSalvySchostVillard2023> <|db-entry> B. É. G. > ACM> 11> <\db-entry|+1NmkRag2bznaymZ|article|vdH:amp> <|db-entry> G. > Complexity> <\db-entry|+1GQhZkrScfYODlE|inproceedings|NeigerRosenkildeSolomatov2020> <|db-entry> J. G. > > <\db-entry|+5gyUr7A16TI54eW|inproceedings|vdH:redbivar> <|db-entry> R. > > <\db-entry|+jZzyy9fWllYOxa|article|CK91> <|db-entry> E. > <\db-entry|+2EIRPFE3ONuyFfN|article|vdH:cyclomult> <|db-entry> J. van der > Complexity> <\db-entry|+1xqpRSxg16lxOwfD|inproceedings|BostanLecerfSchost2003> <|db-entry> G. É. > <\db-entry|+2l3ObZSUfYn|article|AbelardCouvreurLecerf2022> <|db-entry> A. G. > <\db-entry|+1kvxU9Av2XGE1Uwq|phdthesis|Neiger-these2016> <|db-entry> > > > <\db-entry|+2QWNwSQq4Pq|article|Gao1999elements> <|db-entry> > <\db-entry|+C2mCMTwEO5guVw|article|Shoup1992> <|db-entry> > <\db-entry|+2QWNwSQq4Po|article|Shparlinski1996> <|db-entry> > <\db-entry|+2QWNwSQq4Pn|article|Cheng2005> <|db-entry> > <\db-entry|+C2mCMTwEO5guVz|article|Shoup1990> <|db-entry> > <\references> <\collection> > > > > > > > > > > > > > > > > |\>|23>> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > <\auxiliary> <\collection> <\associate|bib> TeXmacs:vdH:book vdH:polexp KedlayaUmans2011 LeBrigandRisler1988 vdH:biamp vdH:genamp BuClSh1997 GathenGerhard2013 WilliamsXuXuZhou2024 WilliamsXuXuZhou2024 NuskenZiegler2004 NuskenZiegler2004 vdH:genamp Neiger2016 vdH:mmx KedlayaUmans2011 vdH:kucomp BhargavaGhoshGuoKumarUmans2022 BhargavaGhoshKumarMohapatra2023 NuskenZiegler2004 vdH:mmeval NeigerSalvySchostVillard2023 NeigerSalvySchostVillard2023 NeigerSalvySchostVillard2023 vdH:amp NeigerRosenkildeSolomatov2020 vdH:amp GathenGerhard2013 NeigerRosenkildeSolomatov2020 vdH:redbivar vdH:biamp vdH:genamp vdH:genamp CK91 vdH:cyclomult GathenGerhard2013 BostanLecerfSchost2003 WilliamsXuXuZhou2024 NuskenZiegler2004 NuskenZiegler2004 NuskenZiegler2004 NuskenZiegler2004 vdH:polexp AbelardCouvreurLecerf2022 vdH:genamp Neiger-these2016 Neiger2016 vdH:genamp vdH:genamp GathenGerhard2013 vdH:polexp vdH:genamp vdH:genamp Gao1999elements Shoup1992 Shparlinski1996 Cheng2005 Shoup1990 <\associate|figure> |2.1>|> Complexity exponent |\|)>> for the evaluation in degree |d> at |N=d*n>> points when |n\3>, via Theorem |->|-0.3em|>|0em||0em|>>. |> |2.2>|> Deterministic and probabilistic complexity exponents for bivariate evaluation in degree |->|-0.3em|>|0em||0em|>>|d> at |d>> points, via Theorems |->|-0.3em|>|0em||0em|>> and |->|-0.3em|>|0em||0em|>>. |> |3.1>|> Complexity exponent |\|)>> for bivariate evaluation in degree |d> at |d>> points via Theorem |->|-0.3em|>|0em||0em|>>. For comparison, we also show the complexity exponent |\|)>> from Theorem |->|-0.3em|>|0em||0em|>>. |> |3.2>|> Complexity exponent |\|)>> for the evaluation of a polynomial in three variables of degree |d> at |d>> points via Theorem. |> <\associate|toc> |math-font-series||font-shape||1.Introduction> |.>>>>|> |1.1.Main results |.>>>>|> > |1.2.Related work |.>>>>|> > |math-font-series||font-shape||2.The Nüsken\UZiegler algorithm> |.>>>>|> |2.1.Separating forms |.>>>>|> > |2.2.Evaluation when |x> is a separating form |.>>>>|> > |2.3.Case of at least three variables |.>>>>|> > |2.4.Bivariate case |.>>>>|> > |math-font-series||font-shape||3.Amortized multivariate evaluation> |.>>>>|> |3.1.Shifted Popov forms |.>>>>|> > |3.2.Admissible orderings |.>>>>|> > |3.3.Minimal polynomials |.>>>>|> > |3.4.Heterogeneous bases |.>>>>|> > |3.5.Amortized evaluation |.>>>>|> > |3.6.Non-amortized evaluation |.>>>>|> > |3.7.Three or more variables |.>>>>|> > |math-font-series||font-shape||Appendix A.Elements of large order> |.>>>>|> |math-font-series||font-shape||Bibliography> |.>>>>|>