Faster multi-point evaluation over any field

Let

be an effective field, so that we have algorithms for the field operations. Given a polynomial

and a tuple

of points, the computation of

is called the problem of multi-point evaluation. The converse problem is called interpolation and takes a candidate support of

as input.

These problems naturally occur in several areas of applied algebra. For instance in [16], 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 [20]. The more specific bivariate case

appears for example in the computation of generator matrices of algebraic geometry error correcting codes [21].

The problem of multi-point evaluation is typically studied in the case when

, 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

, our recent work [14, 17] on amortized multi-point 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.

1.1.Main results

In this paper, the number

of variables is always assumed to be fixed, so the constants hidden in the “

” of our complexity bounds depend on

. For complexity analyses, we will only consider algebraic complexity models like computation trees or RAM machines [5]. The time complexity then measures the number of arithmetic operations and zero-tests in

. The soft-Oh notation

is a shorthand for

; see [9, chapter 25, section 7] for technical details.

The constant

will denote a real value between

and

such that two

matrices over a commutative ring can be multiplied with

ring operations. The current best known bound is

[30]. The constant

will be a real value between 3 and 4 such that the product of a

matrix by a

matrix takes

operations; one may take

[30].

The first line of results, presented in section 2, concerns the derandomization of the Nüsken–Ziegler algorithm [26]. When

our new deterministic bound coincides with their probabilistic one; see Theorem 2.6. For

our deterministic evaluation in degree

points costs

operations in

, whereas the probabilistic version of [26] takes

, which tends to

when

tends to the lower bound

; see Theorems 2.7 and 2.8, and Remark 2.4.

In section 3 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 [17]. In section 3 we provide a careful analysis of the cost of the precomputations. Building on algorithms from [23], it turns out that this can be done with a complexity exponent below the one of linear algebra: see Lemma 3.6. We next use this to derive our main complexity bounds for non-amortized multi-point evaluation: Theorems 3.9 and 3.13. The latter theorem slightly improves upon the Nüsken–Ziegler algorithm when

; see Remark 3.16 for details. We also show that the evaluation at

points can be performed in softly linear time, which again improves upon the Nüsken–Ziegler algorithm.

, then Theorem 3.9 also improves on our deterministic version of the Nüsken–Ziegler algorithm from Theorem 2.7; see Remark 3.10. The comparison with the randomized version is given in Remark 3.11.

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 A, we present a general way to address these issues. Our solution can be implemented with programming languages that support generic programming, such as C++, Mathemagix [18], etc.

1.2.Related work

The general problem of multivariate multi-point evaluation is notoriously hard. If

is a field of finite characteristic, then theoretical algorithms due to Kedlaya and Umans [20] achieve a complexity exponent

, where

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 [13, Conclusion]. Recent advances in this vein are to be found in [2, 3].

The best previously known complexity bound for

and for general fields and input is due to Nüsken and Ziegler [26]: the evaluation of

points can be done using

operations in

, assuming suitable coordinates. So, for

of total degree

, the cost is an expected number of

operations in

, that equals

without fast linear algebra, and that tends to

when

tends to

. We further mention [19] for efficient algorithms for special sets of points

Another recent result for any field

, and for

, is due to Neiger, Salvy, Schost, and Villard [25]. Their algorithm is derived from their fast modular composition algorithm. Given

, and

of degree

, they show how to compute the polynomial

by a probabilistic algorithm of Las Vegas type using an expected number of

operations in

; see [25, Theorem 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

such that

, so

can easily be recovered from

. In [25, section 10.3] it is shown that

can be computed using

operations in

, whenever

has characteristic

, and the input is sufficiently generic. Without fast linear algebra, that is when

, one has

. With the best known value for

, one has

. 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 [15, 24]. These algorithms are amortized in the sense that potentially expensive precomputations as a function of

are allowed. When the dimension

is arbitrary but fixed, the amortized algorithms from [15] generalize the classical univariate “divide and conquer” approach, as presented for instance in [9, chapter 10]. The results in [24] 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 of [12, section 6.2].

The article [14] handles arbitrary (i.e. possibly non-generic) tuples of evaluation points

, while restricting to the amortized bivariate case

and

. New techniques for general dimensions

were presented in [17]. In the present paper we analyze the cost of the precomputations needed in [17]. This is key for our improved complexity bounds for non-amortized multi-point evaluation, especially when

is substantially smaller than

2.The Nüsken–Ziegler algorithm

Throughout this paper, we assume the dimension

to be fixed. So the constants hidden in the

of the complexity estimates will depend on

. We recall that

denotes the tuple of values

. The

-vector space of the polynomials of total degree

will be written

. The cardinality of

is written

We denote by

the time that is needed to compute a product

of two polynomials

of degree

. We make the usual assumptions that

is non-decreasing as a function of

and that

whenever

. Using a variant of the Schönhage–Strassen algorithm [6], it is well known that

. If we restrict our attention to fields

of positive characteristic, then we may even take

[10].

2.1.Separating forms

A linear form

is said to separate 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 joined separating forms for each of the

with

may be computed as follows.

Proof. Recall that

is constant. We proceed by induction on

. If

then the proof is immediate. Assume that

and let

By the induction hypothesis, we may compute

in time

, such that

is a joined separating form for

. Let

Here

stands for the first coordinate of

. If

, then

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

(so

for

) using

operations in

is a separating form for

, then there exist a monic separable polynomial

of degree

and

other polynomials in

such that

If the points of the sequence

are pairwise distinct, it is well-known that these polynomials can be computed using

operations in

, thanks to sub-product tree algorithms; see [9, chapter 10] or [4], for instance. Otherwise we will rely on the following lemma.

Proof. We proceed recursively as follows. If

then the univariate representation is obtained easily in time

. Otherwise, we let

and we recursively compute the univariate representations

and

. We next compute

, and

for

. In this way, the univariate representation of

can be obtained as

, and

2.2.Evaluation when

is a separating form

Let

and

be positive integer parameters such that

and

. We expand the polynomial

to be evaluated as

Input
Output: .
Assumption: is a joined separating form for .

If then set . Otherwise set .

Set .
For , compute the univariate representation of . Note that for all .
For and ,..., , compute

We regard as a matrix over , with entries of degrees .
For , compute and then

for ,..., .
For ,..., , let denote the coefficient of in . We regard as a matrix over , with entries of degrees . Compute
For , compute
Return the concatenation of the vectors for , where stands for the vector with the first coordinates of the points in .

Proof. The assumption on

is needed for step 2. For all

and all points

we verify in step 6 that

operations. Step 6 contributes

to the cost. Step 7 performs univariate multi-point evaluations in total time

. For the complexity of step 5 we distinguish the following cases:

Remark 2.4. The complexity of the product

in step 5 of Algorithm 2.1 actually depends on the ratios of the dimensions of

and

. For simplicity, we have reduced this product to several products of

matrices, whence a complexity bound in terms of

. This choice is slightly sub-optimal if

; see [30]. For instance, if

, then

and the product

can be done faster, using only

Remark 2.5. In their article [26], Nüsken and Ziegler present Algorithm 2.1 in detail only for the case where

and

; see [26, Theorem 8]. They give the complexity bound in terms of

, recalled in Remark 2.4, but also in terms of the partial degrees in

and

. The case where

is only mentioned in the conclusion of [26].

2.3.Case of at least three variables

In general, the form

does not necessarily separate all the

for

. In such degenerate situations, one may apply a suitable change of coordinates before using Algorithm 2.1, provided that the cardinality of

is sufficiently large. In [26, section 6], 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–Ziegler algorithm for

Proof. Assume first that we are given

distinct elements in

. By Lemma 2.1, we may compute a joined separating form

for

using

We replace

. This takes

operations in

thanks to [16, Appendix A, Proposition A.5] and the

distinct elements in

. We next replace

, using

further operations. In this way, we reduce the problem to the case where

separates

. It remains to compute

via Proposition 2.3.

, that is

, then the cost of Algorithm 2.1 is

. If

and

then

(since

) and the cost of Algorithm 2.1 becomes

It remains to deal with the case where

distinct elements in

are not given. We appeal to Proposition A.2: the hypotheses are met since the values returned by the present evaluation algorithm are independent of the

given elements of

or of an algebraic extension of it. The complexity overhead does not exceed (2.2), up to logarithmic factors.

2.4.Bivariate case

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–Ziegler algorithm.

Proof. Assume first that we are given

elements in

. By Lemma 2.1, a joined separating form

for

can be obtained in time

Applying the linear change of coordinates to

and

takes

operations: here we may use [1, Lemma 1] to change the variables independently of the cardinality of

, then the cost of Algorithm 2.1 is

, which is again dominated by (2.3), up to logarithmic factors.

Finally, if we are not given

elements in

, then we apply Proposition A.2, as in the proof of Theorem 2.6.

The next theorem rephrases the probabilistic version of Nüsken and Ziegler for two variables and when

varies.

Proof. In order to find a joined separating form

for

, it suffices to take a random

in the given subset of

. The probability of success for each trial is

; see the proof of Lemma 2.1. So the expected number of trials is

. The rest of the proof is adapted from the one of Theorem 2.7. Alternatively, one may adapt the proof of Theorem 2.6, by noting that the cost to compute a separating form is negligible, if we are allowed to use a randomized algorithm.

3.Amortized multivariate evaluation

In this section, we refine our complexity analysis of the amortized algorithm for the evaluation of multivariate polynomials from [17]. 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

and

denote the polynomial and the tuple of evaluation points, respectively. We also write

for the ideal of

that consists of all polynomials that vanish at

. We recall that the dimension

is fixed.

3.1.Shifted Popov forms

called a shift for the degrees, the

-degree of a row vector

is defined as

is non-zero, then the pivot index of

is the largest index

for which the latter maximum is reached. The entry

is called the pivot, and its degree is the pivot degree. If

is zero, then its pivot index is defined to be zero.

Let

denote a

matrix with entries in

. The matrix

is in -Popov form if the following properties are satisfied:

and

is non-singular, then its pivots are the diagonal elements. In this case,

satisfies the “predictable degree” property:

Given non-constant polynomials

, and given a

matrix

with entries

, Popov forms will be used to compute the kernel of the map

Since the vectors

,...,

are a free family in

, the kernel of

is a free

-module of rank

3.2.Admissible orderings

Let

be the set of monomials

with

. Any polynomial

can uniquely be written as a linear combination

Given a total ordering

, the support of any non-zero polynomial

admits a unique maximal element

that is called the leading monomial of

; the corresponding coefficient

is called the leading coefficient of

. A total ordering

is said to be admissible if

3.3.Minimal polynomials

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

. From [17, Corollary 1], we know that

for

. 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

. By (3.1), this yields

. Using also (3.2), we get

As in the previous sections, the sequence of points

will be split into subsequences

of cardinality

such that

and

. More precisely, until section 3.6, we take

Proof. Without loss of generality, we may order the coordinates such that

, after which we may use the above notation. We write

for the set of polynomials over

with support in

. Let

be the Popov form of the matrix representing the kernel of the projection

Since

is principal,

is a free

-module. Let

be the minimal polynomial of

. Since

is a free family of

, the rank of

. Consequently,

is a non-singular

matrix.

Every row

with

can also be regarded as a polynomial in

, which belongs to

. We have

By the minimality of

and since the

belong to

, the polynomials

with

must be zero and the others must be in

. Consequently,

. By definition (see section 3.1), the pivot index of

for all

. If

is such that

, then the definition of the ordering

ensures that

, where

. It follows that

, whence

. In other words, the leading monomial of

for

is the leading monomial of

. Consequently, the leading monomial of

is the leading monomial of

, where

. Finally, the minimality of

implies that

-proportional to

In order to obtain the Popup form

, we first compute the univariate representations of

for

: this takes

operations in

by Lemma 2.2. The univariate representation of

is given by a monic polynomial

of degree

and polynomials

of degrees

. Now consider the matrix

defined by

for

and

: the entries

can be computed in softly linear time

. Since (3.3) and (3.4) imply

, we may apply Proposition 3.2. We conclude that

can be computed using

3.4.Heterogeneous bases

Given a general weight

and a subset

such that

for all

, we define

to be the weight

with

and

. If

is admissible, then we note that

is again admissible for

where

. We further let

The family of simplest polynomials

is called an heterogenous basis for

and

Proof. The cost for computing a single

is given in Lemma 3.3. On the other hand, we have

, and

by [17, Lemma 2].

Let

and

are still as in (3.4). Assume that

is a power

. A recursive heterogeneous basis for

and

consists of the following data:

We say that linearly independent linear forms

weakly separate

if each of them is a joined separating form for

. We say that they recursively weakly separate

if they weakly separate each of the above

for

and

In order to construct recursive heterogeneous bases, we need coordinates

that recursively weakly separate

. This is the purpose of the following lemma.

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

and

Let

. The standard split of

consists of

sequences of cardinality

. The total number of points in

is at most

. Using (3.7), we verify that

By Lemma 2.1, we may compute a joined separating form

for

, in time

, using the given subset of

. For

, we take

for some

such that

for all distinct points

, for all

. Since

must be different from

elements in

, a suitable

can be found in the given subset of

. In this way,

is a joined separating form for

By construction,

are

-linearly independent. The evaluation of

at all points

takes

operations in

. For each

, the set of unsuitable values for

can be computed using

operations in

3.5.Amortized evaluation

Proof. The case

is well-known; see [9, chapter 10]. So let us assume

. The computation of

and of the recursive heterogeneous basis has been addressed in Lemmas 3.5 (using the element of order

) and 3.6.

Given

and

, the computation of the polynomial

takes

operations in

thanks to [16, Appendix A, Proposition A.5] and the element of order

. By [17, Theorem 5],

can be evaluated at

using

operations in

. Here

is a cost function for multiplying two sparse polynomials

and

, where

is the maximum of the sizes of the supports of

, and

. As detailed in the proof of [17, Theorem 1], we may take

, thanks to the element of order

Proof. Let

. We first handle the case where

. In this way, up to repeating some points in

, we may assume that

is a power of two such that

If we are given an element of order

, then the complexity bounds follow from Lemma 3.7. Otherwise, we may appeal to Proposition A.2 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 A.2.

Finally, if

then we subdivide

into

subsequences of size

, and then repeat the precomputations and the evaluations for each subsequence.

3.6.Non-amortized evaluation

Using the preceding amortized evaluation strategy, we analyze the cost of a single multi-point evaluation in

variables as a function of

Proof. We start with the case

. We subdivide

into subsequences

of cardinality

, where

and

. The evaluations of

for

take

Finally, if

then we subdivide

into

subsequences of size

, so the evaluation cost becomes

Remark 3.11. We have plotted the complexity exponent

for bivariate multi-point evaluation in Figure 3.1 .

Remark 3.12. Comparing with Theorem 2.6, the complexity exponents

and

tend to

and

respectively, when

tends to infinity. If

, then our new bound improves on the Nüsken–Ziegler algorithm for large

. More precisely, we have

3.7.Three or more variables

As in section 2.3, let us now analyze the variant when we apply the amortized evaluation method for

variables to the non-amortized problem for

variables.

Proof. Again, we subdivide

into subsequences

of cardinality

such that

. We expand

as a polynomial in

We apply Theorem 3.8 successively with

in the role of

. The total cost of the precomputations is

Remark 3.16. For

, it is instructive to compare Theorem 3.13 with the best Nüsken–Ziegler style complexity bound

of Remark 2.4:

Appendix A.Elements of large order

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.

Input
Output: An element of of order .

Set , , and .
For each element in do:
1. If then continue the loop of step 2 with the next element in .
2. Compute for .
3. If the order of is , then return .
4. Compute , , , , and .
5. Compute the integers and of the Bézout relation . Replace by and by .
6. If then return .

Proof. Let

denote the current subset of the elements of

that have been handled when entering step 2.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.

then the induction hypothesis is preserved. If the algorithm exits at step 2.c, then the output is clearly correct. Otherwise, the order

can be read off from the computations of step 2.b.

Let

be the prime numbers occurring in the factorization of

, of respective multiplicities

and

, so we have

Some of the

may be zero here. Since

and

are at most

, the

and

are at most

. From

Similarly, if

is a prime divisor of

, then

. Consequently,

has order

. In particular, if the algorithm exits in step 2.f, then the output is correct. From

we note that

and

divide

. Therefore the induction hypothesis again holds at the end of step 2.

Since the orders of the elements of

divide

, they are roots of the polynomial

, whence

. This shows that the algorithm works as expected.

Steps 2.a, 2.d, and 2.e take

operations in

. Step 2.b takes

operations. In step 2.e, the integer

is at least doubled, so step 2.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 A.1 is suboptimal. In particular, if the characteristic of

is zero, then

has always order

. If

is a finite field, then

is cyclic and primitive elements can be obtained more efficiently; see [8, 28, 29] for instance, but also the survey [7]. As an advantage, Algorithm A.1 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 A.1 even without any piece of information about

Proof. We are interested in computing an element of order

. First, we can compute the sequence of integers

using

additions, and then determine whether

or not. If

, then we can use Algorithm A.1 in order to obtain an element

of order

. In this case,

simply runs

with

Otherwise,

. We shall compute in a sufficiently large algebraic extension of

as follows. Let

be the first integer such that

Thanks to [27, Theorem 3.2], we may deterministically construct a monic irreducible polynomial

of degree

using

operations in

. In this way,

is the finite field with

elements. We can enumerate

non-zero elements of

and then use Algorithm A.1 in order to obtain an element

of order

. We regard

as a polynomial in

of degree

Now we regard

as a computation tree over

, using

in place of the input element of order

. While executing

for given input in

, sums and products can be lifted straightforwardly to

: elements of

are represented by polynomials of degree

. When testing whether an element

Note that

remains embedded in

whenever

is replaced by any non-trivial factor over

. In particular, the order of

remains

after any such replacement. At the end, we thus obtain the evaluation of

over

, where

is a non-constant factor of the original

. This proves the correctness of our method.

Computing

takes

operations thanks to Proposition A.1. The evaluation of

over

requires

ring operations or extended gcd computations for polynomials over

of degree at most

. This contributes

to the cost. The overall cost is therefore as claimed.

Bibliography

[1]: S. Abelard, A. Couvreur, and G. Lecerf. Efficient computation of Riemann–Roch spaces for plane curves with ordinary singularities. Appl. Algebra Eng. Commun. Comput., 35(6):739–804, 2024.
[2]: V. Bhargava, S. Ghosh, Z. Guo, M. Kumar, and C. Umans. Fast multivariate multipoint evaluation over all finite fields. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 221–232. New York, NY, USA., 2022. IEEE.
[3]: V. Bhargava, S. Ghosh, M. Kumar, and C. K. Mohapatra. Fast, algebraic multivariate multipoint evaluation in small characteristic and applications. J. ACM, 2023. Article 42.
[4]: A. Bostan, G. Lecerf, and É. Schost. Tellegen's principle into practice. In Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation, ISSAC '03, pages 37–44. New York, NY, USA, 2003. ACM.
[5]: P. Bürgisser, M. Clausen, and M. A. Shokrollahi. Algebraic Complexity Theory, volume 315 of Grundlehren der Mathematischen Wissenschaften. Springer-Verlag, 1997.
[6]: D. G. Cantor and E. Kaltofen. On fast multiplication of polynomials over arbitrary algebras. Acta Inform., 28:693–701, 1991.
[7]: Q. Cheng. On the construction of finite field elements of large order. Finite Fields their Appl., 11(3):358–366, 2005.
[8]: S. Gao. Elements of provable high orders in finite fields. Proc. Am. Math. Soc., 127(6):1615–1623, 1999.
[9]: J. von zur Gathen and J. Gerhard. Modern computer algebra. Cambridge University Press, New York, 3rd edition, 2013.
[10]: D. Harvey and J. van der Hoeven. Faster polynomial multiplication over finite fields using cyclotomic coefficient rings. J. Complexity, 54:101404, 2019.
[11]: J. van der Hoeven. The Jolly Writer. Your Guide to GNU TeXmacs. Scypress, 2020.
[12]: J. van der Hoeven and R. Larrieu. Fast reduction of bivariate polynomials with respect to sufficiently regular Gröbner bases. In C. Arreche, editor, Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation, ISSAC '18, pages 199–206. New York, NY, USA, 2018. ACM.
[13]: J. van der Hoeven and G. Lecerf. Fast multivariate multi-point evaluation revisited. J. Complexity, 56:101405, 2020.
[14]: J. van der Hoeven and G. Lecerf. Amortized bivariate multi-point evaluation. In M. Mezzarobba, editor, Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation, ISSAC '21, pages 179–185. New York, NY, USA, 2021. ACM.
[15]: J. van der Hoeven and G. Lecerf. Fast amortized multi-point evaluation. J. Complexity, 67:101574, 2021.
[16]: J. van der Hoeven and G. Lecerf. On the complexity exponent of polynomial system solving. Found. Comput. Math., 21:1–57, 2021.
[17]: J. van der Hoeven and G. Lecerf. Amortized multi-point evaluation of multivariate polynomials. J. Complexity, 74:101693, 2022.
[18]: J. van der Hoeven, G. Lecerf, B. Mourrain et al. Mathemagix. 2002. http://www.mathemagix.org.
[19]: J. van der Hoeven and É. Schost. Multi-point evaluation in higher dimensions. Appl. Alg. Eng. Comm. Comp., 24(1):37–52, 2013.
[20]: K. S. Kedlaya and C. Umans. Fast polynomial factorization and modular composition. SIAM J. Comput., 40(6):1767–1802, 2011.
[21]: D. Le Brigand and J.-J. Risler. Algorithme de Brill–Noether et codes de Goppa. Bulletin de la société mathématique de France, 116(2):231–253, 1988.
[22]: V. Neiger. Bases of relations in one or several variables: fast algorithms and applications. PhD thesis, École Normale Supérieure de Lyon (France) – University of Waterloo (Canada), 2016. https://tel.archives-ouvertes.fr/tel-01431413.
[23]: V. Neiger. Fast computation of shifted Popov forms of polynomial matrices via systems of modular polynomial equations. In Proceedings of the ACM on International Symposium on Symbolic and Algebraic Computation, ISSAC '16, pages 365–372. New York, NY, USA, 2016. ACM.
[24]: V. Neiger, J. Rosenkilde, and G. Solomatov. Generic bivariate multi-point evaluation, interpolation and modular composition with precomputation. In A. Mantzaflaris, editor, Proceedings of the 45th International Symposium on Symbolic and Algebraic Computation, ISSAC '20, pages 388–395. New York, NY, USA, 2020. ACM.
[25]: V. Neiger, B. Salvy, É. Schost, and G. Villard. Faster modular composition. J. ACM, 71(2):1–79, 2023. Article No. 11.
[26]: M. Nüsken and M. Ziegler. Fast multipoint evaluation of bivariate polynomials. In S. Albers and T. Radzik, editors, Algorithms – ESA 2004. 12th Annual European Symposium, Bergen, Norway, September 14-17, 2004, volume 3221 of Lect. Notes Comput. Sci., pages 544–555. Springer Berlin Heidelberg, 2004.
[27]: V. Shoup. New algorithms for finding irreducible polynomials over finite fields. Math. Comp., 54(189):435–447, 1990.
[28]: V. Shoup. Searching for primitive roots in finite fields. Math. Comp., 58:369–380, 1992.
[29]: I. Shparlinski. On finding primitive roots in finite fields. Theor. Comput. Sci., 157(2):273–275, 1996.
[30]: V. V. Williams, Y. Xu, Z. Xu, and R. Zhou. New bounds for matrix multiplication: from alpha to omega. In D. P. Woodruff, editor, Proceedings of the 2024 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 3792–3835. Philadelphia, PA 19104 USA, 2024. SIAM.

1.Introduction

1.1.Main results

1.2.Related work

2.The Nüsken–Ziegler algorithm

2.1.Separating forms

2.2.Evaluation when is a separating form

2.3.Case of at least three variables

2.4.Bivariate case

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

Appendix A.Elements of large order

Bibliography