Fast computation of generic bivariate resultants

Joris van der Hoevena, Grégoire Lecerfb

CNRS, École polytechnique, Institut Polytechnique de Paris

Laboratoire d'informatique de l'École polytechnique (LIX, UMR 7161)

1, rue Honoré d'Estienne d'Orves

Bâtiment Alan Turing, CS35003

91120 Palaiseau, France

a. Email: vdhoeven@lix.polytechnique.fr

b. Email: lecerf@lix.polytechnique.fr

Preliminary version of November 4, 2023

. This paper is part of a project that has received funding from the French “Agence de l'Innovation de Défense”.

We prove that the resultant of two “sufficiently generic” bivariate polynomials over a finite field can be computed in quasi-linear expected time, using a randomized algorithm of Las Vegas type. A similar complexity bound is proved for the computation of the lexicographical Gröbner basis for the ideal generated by the two polynomials.

Keywords: complexity, algorithm, computer algebra, resultant, elimination, multipoint evaluation

1.Introduction

The efficient computation of resultants is a fundamental problem in elimination theory and for the algebraic resolution of systems of polynomial equations. Given an effective field , it is well known [10, chapter 11] that the resultant of two univariate polynomials of respective degrees can be computed using field operations in . Here the soft-Oh notation is an abbreviation for , for any expression .

Given two bivariate polynomials of respective total degrees , their resultant in can be computed in time ; e.g. see [20, Theorem 25] and references in that paper. If , then this corresponds to a complexity exponent of in terms of input/output size. An important open question in algebraic complexity theory is whether this exponent can be lowered.

In the present paper, we consider the case when and are “sufficiently generic”. If the coefficients of and are chosen at random in a finite field with sufficiently many elements, then this will be the case with high probability. Under a suitable hypothesis of “grevlex-lex-generic position” (defined below) and assuming the random access memory (RAM) bit complexity model, our main result is the following theorem:

Theorem 1. Let be a fixed rational number. Let be two polynomials of respective total degrees over a finite field . If and are in grevlex-lex-generic position, then can be computed in expected time

using a randomized algorithm of Las Vegas type.

A major result in a similar direction has recently been obtained by Villard [25]. For a general effective field , and under different genericity assumptions, he proposed an algorithm that computes the resultant in of two polynomials of degree in and degree in using operations in . Here is the usual exponent for matrix multiplication (such that two matrices over can be multiplied using operations in ). Le Gall has shown in [19] that one may take .

Relationship to Gröbner bases
Resultants are related to elimination theory. Throughout the paper, we assume that the reader is familiar with the basic theory of Gröbner bases, as found in standard text books [4, 10], so we only briefly recall basic terminology.

Let still be a general effective field. Two common monomial orderings on the polynomial ring are the lexicographical ordering and the reverse graded lexicographical ordering defined by

We say that and are in lex-generic ( resp. grevlex-generic ) position if the leading monomials of the reduced Gröbner basis of with respect to ( resp. ) coincide with the ones that we would obtain when taking symbolic parameters for the coefficients of and ; see Figure 1

Figure 1. Illustration of the Gröbner stairs for and in generic position with respect to (left) and (right) in the case when and .

. We say that and are in grevlex-lex-generic position when they are both in lex-generic and grevlex-generic position. Notice that we do not require the ideal to be radical over the algebraic closure of .

The relationship between resultants and Gröbner bases is the following: if and are in lex-generic position, then the reduced Gröbner basis of with respect to consists of the minimal polynomial of , which is a constant multiple of , and the polynomial for some with ; see section 4.1.

Assuming that and are in grevlex-generic position, the recent result from [12] is an algorithm to compute a concise representation [12, Definition 14] of the Gröbner basis of with respect to using operations in , while conserving its main properties; see section 3. Note that the Gröbner basis in its usual representation generically requires storage, so its computation is too expensive for our purposes.

If we were able to rapidly convert a Gröbner basis for into a new one for , then this would allow us to compute resultants in softly linear time. Unfortunately, traditional “change-of-ordering” algorithms such as the FGLM algorithm [6, 7] rely on linear algebra, and do not run in softly linear time. For our proof of Theorem 1 in section 6, we will instead rely on a bivariate counterpart of Kedlaya–Umans' algorithm for modular composition [16]. This technique does not work for general effective fields , which explains the restriction to the case when is a finite field in Theorem 1.

Specific fields
For , Mehrabi and Schost [21] showed how to compute a basis of with respect to by means of a probabilistic algorithm of Monte Carlo type with a nearly optimal bit complexity bound. Their bound is optimal when the coefficients grow as expected in the worst case and their method depends on Kedlaya–Umans as well. This approach has been generalized to higher dimensions in [14]. The probabilistic aspect comes from the need of a sufficiently generic linear change of the variables. The best known deterministic complexity bound can be found in [2].

Over finite fields, Poteaux and Schost [22, Theorem 1.2] achieved the computation of bivariate lexicographical bases with bit complexity in the special case when or belongs to , provided that the underlying characteristic is greater than , and that is radical, yet without genericity assumption. Their method extends to an arbitrary number of variables.

Outline of our contribution
The proof of Theorem 1 relies on a sequence of reductions, using a novel combination of classical and more recent techniques. In sections 2 and 3, we first recall basic notations and the required results from [12] about concise Gröbner bases.

Assuming from there on that and are in grevlex-lex-generic position, we recall in section 4 how to reduce the computation of the resultant to the computation of the minimal polynomial of the multiplication endomorphism by in . This minimal polynomial can be computed with high probability using Wiedemann's algorithm, provided that we have an algorithm for the transposed map of evaluating a univariate polynomial at in . This kind of strategy has been used several times before in computer algebra [15, 22-24]; see also [10, chapter 12, section 4].

The evaluation of a univariate polynomial at in can be regarded as a bivariate modular composition problem. Exploiting the fact that multiplication in is fast (thanks to the concise Gröbner basis representation), we show in section 5 how to reduce this problem to multivariate multipoint evaluation. For this reduction, we mostly follow Kedlaya and Umans, along the same lines as in the proof of [16, Theorem 3.1] for univariate modular composition; refinements can be found in [13].

At that point, we restrict ourselves to the case when is a finite field, so as to benefit from Kedlaya and Umans' fast algorithm for multipoint evaluation and its transpose [16]. In section 6, this allows us to conclude the proof of Theorem 1.

The final section 7 contains a few further notes and directions for future research. In particular, we show that the full lexicographical Gröbner basis can be computed in a similar time as the resultant, with ideas similar to [22] and [8, Algorithm 2]. Finally we quantify the genericity hypotheses in a more precise manner.

2.Preliminaries

Computational model
Throughout this paper, is an effective field. Most of our algorithms work in the algebraic complexity models of straight-line programs (SLPs) or computation trees [3], in which execution times correspond to the required number of field operations in . The genericity assumptions imply that non-trivial zero tests always fail, so the straight-line program framework actually suffices.

In section 6, where we prove Theorem 1, we specialize to become a finite field . From that point on, we assume a RAM bit complexity model and recall that field operations in can be performed in softly linear time .

Transposition principle
Given a finite dimensional -vector space of that admits as a basis, it is convenient to mentally represent elements of as column vectors with respect to this basis and linear forms as row vectors. Linear maps between two vector spaces of this type correspond to matrices.

Writing for the set of linear forms , the transpose of a linear map is the linear map such that for all . If can be computed by a linear SLP over of length , then it is well-known [3, Theorem 13.20] that can be computed by an SLP of length . This “transposition principle” is in general easy to be put into practice on concrete programs, as exemplified in [1]. Roughly speaking, the program is regarded as a composition of individual steps that are easy to transpose. For the transposition of a composition , where is another -linear map, we next apply the usual formula .

Gröbner bases
Given indeterminates and positive integers , we define

Consider a Gröbner basis of an ideal for some term ordering on the set of monomials . We write for the -vector space of polynomials that are reduced with respect to . The reduced monomials in form a basis for and correspond to the monomials “under the Gröbner stairs”. In other words, consists of the monomials that are not divisible by the leading monomial of an element in . We also write

for the map that computes the normal form of a polynomial with respect to , i.e. the unique polynomial in such that .

3.Concise representation of the quotient algebra

In the remainder of this paper, let be two polynomials of total degrees , in grevlex-lex-generic position. We write for the ideal generated by and , and for the corresponding quotient algebra. Let us start by recalling several facts from [12].

Gröbner basis
The reduced Gröbner basis of with respect to consists of polynomials with leading monomials ; see [9], [12, section 2], and Figure 1.

Concise Gröbner bases
[12, section 4 and Theorem 28] Using operations in , one may compute the concise representation of the Gröbner basis of with respect to . The leading monomials of and coincide for , but are not necessarily reduced. Furthermore, are not explicitly written out (since this typically requires coefficients in ); this is why we need to represent in a concise way, while ensuring that no essential information is lost.

Normal form
[12, section 5 and Proposition 31] Given a polynomial with and , we may compute its normal form with respect to using operations in . Recall that is the unique element in with ; in particular, and coincide.

Checking the genericity assumption
By means of [12, Remark 4, Theorem 28, and Proposition 31], the condition that and are indeed in grevlex-generic position can be checked using operations in by running the basis computation and aborting when an irregularity occurs.

Multiplication in the quotient algebra
[12, section 6.2 and Theorem 33] Assume that the concise Gröbner basis of has been computed. We represent elements in the quotient algebra by normal forms in . Given , we may now compute using operations in , since and . By what precedes, we may therefore compute in time . In other words, products in can be computed in softly linear time.

4.Reduction to bivariate modular composition

As above, and are polynomials in in grevlex-lex-generic position, , and .

4.1.Resultants and minimal polynomials

Consider the -linear multiplication map . It is known that the characteristic polynomial of this map equals for some ; see for instance [5, Proposition 2.7] applied with and . When all the zeros of are regular, is separable and the latter property follows more straightforwardly by comparing the sets of roots of and of via the Stickelberger eigenvalue theorem [18].

On the other hand, since and are in lex-generic position, we have

We introduce the minimal polynomial of as the monic polynomial of minimal degree such that , or, equivalently, . In particular, coincides with the unique element of the reduced Gröbner basis of for that belongs to .

Lemma 2. With and in grevlex-lex-generic position, we have . In addition, if , then can be recovered from using operations in .

Proof. We always have . The polynomials and coincide whenever ; this is the case if and only if and are in lex-generic position.

Once is known, since , we may find a such that using operations in , by means of fast multipoint evaluation. Then the above value can be computed using further operations, as

From and , we deduce .

The above discussion shows that the computation of reduces to the determination of .

4.2.Wiedemann's algorithm

We use Wiedemann's algorithm and the transposition principle for the computation of , as follows:

4.3.Probability analysis

The above polynomials and coincide if, and only if, for any irreducible factor of . Now given an irreducible factor of , we have . A random linear form as above annihilates a fixed non-zero element of with probability at most . The probability that annihilates is therefore bounded by . We conclude that the probability that none of the irreducible factors of annihilates is at least

The algorithm of the previous subsection and the present probability analysis are summarized in the following lemma.

Lemma 3. Assume that and are in grevlex-lex-generic position and that . Then the computation of takes an expected number of operations in plus an expected number of computations of sequences (1) for different values of .

5.Reduction to multipoint evaluation

In this section, we show how to efficiently reduce the evaluation of to multivariate multipoint evaluation. We mostly follow the same Kronecker segmentation strategy as in [13, 16, 22] for modular composition.

5.1.Kronecker segmentation

Given an integer that will be specified later, let be the smallest integer such that . We define the Kronecker map

as the restriction to of the unique morphism of -algebras that sends to for . Notice that is bijective and that both and its inverse can be computed in linear time with respect to the monomial bases.

Let and be upper bounds for the degrees in and of elements in . We may compute

using binary powering. By what has been said in section 3, this requires operations in . For any and , we notice that

Let , , and

Note that and indeed hold for . It follows that

(2)

5.2.Evaluation-interpolation

We will compute the map using evaluation-interpolation. Assume for the time being that and let be pairwise distinct points. Define for . Setting , , consider the evaluation map

which is a -linear bijection. Using traditional univariate evaluation-interpolation in each coordinate [10, chapter 10], both and its inverse can be evaluated using SLPs of length over . In particular, we can compute

(3)

in time . We next define the map

Then we have

Combined with (2), this yields

(4)

6.Fast computation of resultants

In section 4, we have reduced the computation of bivariate resultants to the evaluation of the transposed map of . In section 5 the evaluation of has been reduced to multivariate multipoint evaluation. We first recall how to perform the latter evaluation using algorithms by Kedlaya and Umans. We next combine the above reductions with the transposition principle and prove our main result.

6.1.Fast multipoint evaluation

Kedlaya and Umans designed various algorithms for modular composition and multipoint evaluation [16]. They also gave algorithms for the transposed operations. For the computation of and its transpose, we will rely on the following result, which is a direct consequence of [16, Corollary 4.5 and Theorem 7.6]:

Theorem 4. Let be a fixed rational number. Given and evaluation points such that , there exists an algorithm that outputs for , and that runs in time

The transpose of the linear map can be computed with the same complexity.

Note that [16, Corollary 4.5 and Theorem 7.6] are actually stated in an more precise manner and that we voluntarily simplified the presentation. We also refer to [13] for some recent refinements.

6.2.Evaluating and

Assume from now on that . Before we prove our main result, let us first study the complexity of evaluating the transpose of . Recall that the computation of a sequence as in (1) reduces to one such evaluation.

Proposition 5. Let be a constant, thought to be small. Assume that and that the concise representation of and the sets of (3) have been precomputed. Then one evaluation of or of its transpose takes time .

Proof. We let

and verify the following bounds:

Theorem 4 therefore implies that and can be computed in time .

In the previous sections, we have already shown that , and can be computed using operations over . Combining this with (4), it follows that one evaluation of takes time .

Using our genericity assumptions, we also observed that these computations can be carried out by linear SLPs over . In view of the transposition principle (see section 2), it follows that , and can also be computed using operations over . Combining this with (4), we conclude that

can be computed in time as well.

6.3.Proof of Theorem 1

Let us first reduce to the case when and . Let be the smallest power of such that and . Whenever , we replace by the extension field . Since , the construction of takes bit complexity , e.g. by using [10, Corollary 14.39], and the overhead involved by this extension only concerns hidden logarithmic factors in the complexity bounds.

Consequently from now and are satisfied. The concise representation of the Gröbner basis of for takes operations in , as recalled in section 3. With as in the proof of Proposition 5, we compute in time , and then in time , as seen in section 5.2. The minimal polynomial of can therefore be obtained in expected time , thanks to the combination of Lemma 3 and Proposition 5. We finally deduce from using Lemma 2 and further operations in .

7.Further notes

7.1.Parametrization

Recall from section 4.1 that coincides with the unique element in of the Gröbner basis of with respect to and up to a constant multiple with the resultant . It is an interesting question whether the complete basis can actually be computed fast.

Now if and are in lex-generic position, then contains exactly one other element besides , which is of the form with . Let us show how to recover this parametrization in expected time

One technique for doing this goes back to Kronecker [17]: it performs a first order deformation in order to compute the minimal polynomial of modulo ; see for instance in [11, section 2]. In the present paper, we appeal to an other known method relying once more on power projections; as in [8, Algorithm 2], for instance.

For this purpose, let be the linear form that has successfully led to the computation of and let be the reciprocal of . We compute the polynomial of degree such that and are coprime and

Now let be the linear form that sends to . This form can be computed in softly linear time by the transposition principle. Note that the sequence

(5)

may be obtained in the same way as (1), in time , thanks to Proposition 5. The sequences (1) and (5) are related by the identity

where . It follows that

is a polynomial of degree . Since and are coprime, we finally obtain the reciprocal of using

This takes further operations in .

7.2.On the genericity assumptions

We already noted in section 3 that the grevlex-generic position can be checked using operations in . Let us now quantify the genericity of the grevlex-generic position. Write and . As in [12], we define and , which both belong to . By [12, Remark 4] and thanks to the relationship between the Euclidean remainder sequence and the subresultant polynomials (see for instance [20, Corollary 3]), and are in grevlex-generic position if and only if the following conditions are satisfied:

  1. and ,

  2. The subresultant coefficient in degree of and is non-zero for . This subresultant is the determinant of a square matrix of size whose entries are coefficients of and ; see for instance [10, chapter 6].

  3. The system admits exactly solutions counting multiplicities, or equivalently the coefficient of in is non-zero; see for instance [5, Proposition 2.7] applied with and . This coefficient has total degree in the coefficients of and .

Overall, there exists a polynomial in of total degree at most

such that implies the grevlex-generic position of and .

In order to show that is not the zero polynomial, we construct the auxiliary sequence of polynomials recursively by and starting with with and , so , , , etc. We verify by induction that for . Taking

(6)

contains , contains , , and . In this way is the Euclidean remainder sequence of and . By [20, Corollary 3] all the subresultant coefficients of and are non-zero. In addition, since and are homogeneous, it is easy to verify that is a non-zero multiple of . Consequently is not identically zero.

A sufficient (but non necessary condition) to ensure that and are in lex-generic position is that is separable. The coefficients of have degree in the coefficients of and . Consequently the discriminant of , written , has total degree . When the lex-generic position holds. To see that is not identically zero it suffices to take and : then is separable for sufficiently generic values of .

7.3.Possible extensions

Our method can be extended in several directions, as we will briefly outline now.

Acknowledgments.
We thank the anonymous referees for their useful comments.

Bibliography

[1]

A. Bostan, G. Lecerf, and É. Schost. Tellegen's principle into practice. In Hoon Hong, editor, ISSAC '03: Proceedings of the 2003 International Symposium on Symbolic and Algebraic Computation, pages 37–44. New York, NY, USA, 2003. ACM.

[2]

Y. Bouzidi, S. Lazard, G. Moroz, M. Pouget, F. Rouillier, and M. Sagraloff. Solving bivariate systems using rational univariate representations. J. Complexity, 2016.

[3]

P. Bürgisser, M. Clausen, and M. A. Shokrollahi. Algebraic Complexity Theory, volume 315 of Grundlehren der Mathematischen Wissenschaften. Springer-Verlag, 1997.

[4]

D. Cox, J. Little, and D. O'Shea. Ideals, varieties, and algorithms: an introduction to computational algebraic geometry and commutative algebra. Springer Science & Business Media, 2nd edition, 2013.

[5]

C. Durvye and G. Lecerf. A concise proof of the Kronecker polynomial system solver from scratch. Expo. Math., 26(2), 2007.

[6]

J.-C. Faugère, P. Gaudry, L. Huot, and G. Renault. Sub-cubic change of ordering for Gröbner basis: a probabilistic approach. In K. Nabeshima, editor, ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, pages 170–177. New York, NY, USA, 2014. ACM.

[7]

J.-C. Faugère, P. Gianni, D. Lazard, and T. Mora. Efficient computation of zero-dimensional Gröbner bases by change of ordering. J. Symbolic Comput., 16(4):329–344, 1993.

[8]

J.-C. Faugère and C. Mou. Sparse FGLM algorithms. J. Symbolic Comput., 80:538–569, 2017.

[9]

A. Galligo. A propos du théorème de préparation de Weierstrass. In F. Norguet, editor, Fonctions de plusieurs variables complexes, volume 409 of Lecture Notes in Math., pages 543–579. Springer, Berlin, Heidelberg, 1974.

[10]

J. von zur Gathen and J. Gerhard. Modern Computer Algebra. Cambridge University Press, 3rd edition, 2013.

[11]

B. Grenet, J. van der Hoeven, and G. Lecerf. Deterministic root finding over finite fields using Graeffe transforms. Appl. Algebra Engrg. Comm. Comput., 27(3):237–257, 2016.

[12]

J. van der Hoeven and R. Larrieu. Fast Gröbner basis computation and polynomial reduction for generic bivariate ideals. Appl. Algebra Engrg. Comm. Comput., 30:509–539, 2019.

[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. On the complexity exponent of polynomial system solving. Found. Comput. Math., 2020. https://doi.org/10.1007/s10208-020-09453-0.

[15]

E. Kaltofen and V. Shoup. Subquadratic-time factoring of polynomials over finite fields. Math. Comp., 67(223):1179–1197, 1998.

[16]

K. S. Kedlaya and C. Umans. Fast polynomial factorization and modular composition. SIAM J. Comput., 40(6):1767–1802, 2011.

[17]

L. Kronecker. Grundzüge einer arithmetischen Theorie der algebraischen Grössen. J. reine angew. Math., 92:1–122, 1882.

[18]

D. Lazard. Résolution des systèmes d'équations algébriques. Theoret. Comput. Sci., 15(1):77–110, 1981.

[19]

F. Le Gall. Powers of tensors and fast matrix multiplication. In K. Nabeshima, editor, ISSAC '14: Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, pages 296–303. New York, NY, USA, 2014. ACM.

[20]

G. Lecerf. On the complexity of the Lickteig–Roy subresultant algorithm. J. Symbolic Comput., 2019.

[21]

E. Mehrabi and É. Schost. A softly optimal Monte Carlo algorithm for solving bivariate polynomial systems over the integers. J. Complexity, 34:78–128, 2016.

[22]

A. Poteaux and É. Schost. Modular composition modulo triangular sets and applications. Comput. Complex., 22(3):463–516, 2013.

[23]

V. Shoup. Fast construction of irreducible polynomials over finite fields. J. Symbolic Comput., 17(5):371–391, 1994.

[24]

V. Shoup. Efficient computation of minimal polynomials in algebraic extensions of finite fields. In Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation, ISSAC '99, pages 53–58. New York, NY, USA, 1999. ACM.

[25]

G. Villard. On computing the resultant of generic bivariate polynomials. In C. Arreche, editor, ISSAC '18: Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic Computation, pages 391–398. New York, NY, USA, 2018. ACM.