Fast computation of generic bivariate
resultants |
|
| 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.
|
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:
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 
.
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
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.
, 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.
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.
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 
.
-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 
.
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 
.
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].
of with respect to consists of
polynomials 
with leading monomials 
; see [9], [12,
section 2], and Figure 1.
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.
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.
and
are indeed in grevlex-generic position can be checked using operations in by running the
basis computation and aborting when an irregularity occurs.
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.
As above, and are
polynomials in in grevlex-lex-generic position,
, and .
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
.
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 
.
We use Wiedemann's algorithm and the transposition principle for the
computation of , as follows:
We first select a random linear form 
.
More precisely, assuming that 
,
we select a finite subset 
of size 
and take 
to be a row vector
with random entries from 
.
Taking 
, we define the
map
We will explain how to evaluate 
efficiently
in section 5.
Then we compute the sequence
 |
(1) |
This task is an extension of the usual “power
projection” problem to the bivariate case, since it
corresponds to one evaluation of the transposed map of :
Using the fast variant of the Berlekamp–Massey algorithm [10, chapter 12, Algorithm 12.9 combined with the extended
half-gcd algorithm], we determine the linear recurrence relation of
smallest order 
satisfied by the sequence (1). Stated otherwise, this means that we compute the monic
polynomial 
of minimal degree such that
The set of polynomials 
for which 
for 
is closed under gcds and
clearly contains . This
implies that we always have 
.
If 
, then we are sure
that 
. The next
subsection reminds why this happens with high probability.
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.
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 
.
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.
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
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
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.
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]:
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.
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.
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.
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 .
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 .
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:
and 
,
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].
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 
.
Our method can be extended in several directions, as we will briefly outline now.
With more work, we expect that the lex-genericity assumption can be
relaxed somewhat, e.g. to the case when the
Gröbner basis for consists of
polynomials of degree 
in . Indeed, using linear algebra techniques
inspired by Wiedemann's algorithm, the idea would be to recover the
characteristic polynomial from the minimal polynomial by determining
the multiplicities of the square-free factors.
Similarly, and as already noticed in [12], it might be
possible to relax the grevlex-genericity assumption somewhat,
e.g. to the case when the Gröbner basis for consists of and
polynomials with leading monomials of the form 
.
In [16, section 6], Kedlaya and Umans proposed an algebraic algorithm for multivariate multipoint evaluation (and its transpose, in virtue of the transposition principle). These algorithms are mainly interesting in small characteristic, in which case they can be used instead of the ones from Theorem 4. These algebraic algorithms can also be generalized to more general finite fields, provided that one has an operation for the Frobenius map and its inverse.
Unfortunately, we are not aware of any efficient implementations of
Kedlaya–Umans' algorithms; see [13] for a
discussion about the (very large) input sizes for which the
complexity bounds would become competitive. For the time being, we
therefore do not expect Theorem 1 to induce faster
practical implementations of bivariate resultants. Nevertheless, it
should be noticed that the maps and can both be regarded as black boxes for our
algorithm: whenever a faster algorithm for one of these maps does
become available, our method might be relevant for practical
applications.
Using Chinese remaindering and rational reconstruction, the approach
of this paper to compute lexicographical Gröbner bases should
extend to the case when and
have coefficients in 
. In
the generic case, this would provide an interesting, more direct
alternative of Las Vegas type for [21] and [14].
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.
Y. Bouzidi, S. Lazard, G. Moroz, M. Pouget, F. Rouillier, and M. Sagraloff. Solving bivariate systems using rational univariate representations. J. Complexity, 2016.
P. Bürgisser, M. Clausen, and M. A. Shokrollahi. Algebraic Complexity Theory, volume 315 of Grundlehren der Mathematischen Wissenschaften. Springer-Verlag, 1997.
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.
C. Durvye and G. Lecerf. A concise proof of the Kronecker polynomial system solver from scratch. Expo. Math., 26(2), 2007.
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.
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.
J.-C. Faugère and C. Mou. Sparse FGLM algorithms. J. Symbolic Comput., 80:538–569, 2017.
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.
J. von zur Gathen and J. Gerhard. Modern Computer Algebra. Cambridge University Press, 3rd edition, 2013.
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.
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.
J. van der Hoeven and G. Lecerf. Fast multivariate multi-point evaluation revisited. J. Complexity, 56:101405, 2020.
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.
E. Kaltofen and V. Shoup. Subquadratic-time factoring of polynomials over finite fields. Math. Comp., 67(223):1179–1197, 1998.
K. S. Kedlaya and C. Umans. Fast polynomial factorization and modular composition. SIAM J. Comput., 40(6):1767–1802, 2011.
L. Kronecker. Grundzüge einer arithmetischen Theorie der algebraischen Grössen. J. reine angew. Math., 92:1–122, 1882.
D. Lazard. Résolution des systèmes d'équations algébriques. Theoret. Comput. Sci., 15(1):77–110, 1981.
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.
G. Lecerf. On the complexity of the Lickteig–Roy subresultant algorithm. J. Symbolic Comput., 2019.
E. Mehrabi and É. Schost. A softly optimal Monte Carlo algorithm for solving bivariate polynomial systems over the integers. J. Complexity, 34:78–128, 2016.
A. Poteaux and É. Schost. Modular composition modulo triangular sets and applications. Comput. Complex., 22(3):463–516, 2013.
V. Shoup. Fast construction of irreducible polynomials over finite fields. J. Symbolic Comput., 17(5):371–391, 1994.
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.
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.
and 
.
