
Let be the reduced Gröbner basis of a zerodimensional ideal of bivariate polynomials over an effective field . Modulo suitable regularity assumptions on and suitable precomputations as a function of , we prove the existence of a quasioptimal algorithm for the reduction of polynomials in with respect to . Applications include fast algorithms for multiplication in the quotient algebra and for conversions due to changes of the term ordering.

Let be an effective field and consider an algebra where is a finitely generated ideal. For actual computations in , we have three main tasks:
define a nonambiguous representation for elements in ;
design a multiplication algorithm for ;
show how to convert between different representations for elements in .
Fast polynomial arithmetic based on FFTmultiplication allows for a quasioptimal solution in the univariate case. However, reduction modulo an ideal of multivariate polynomials is nontrivial.
The most common approach for computations modulo ideals of polynomials is based on Gröbner bases. This immediately solves the first task, using the fact that any polynomial admits a unique normal form modulo a given Gröbner basis [3]. The second task is solved by reducing the product of two polynomials modulo the Gröbner basis. Finally, given a Gröbner basis with respect to a first term ordering, one may use the FGLM algorithm [8] to compute a reduced Gröbner basis with respect to a second term ordering; algorithms for the corresponding conversions are obtained as a byproduct.
There is an abundant literature on efficient algorithms for the computation of Gröbner bases; see for example [6, 7, 8] and references therein. Although the worst case complexity is known to be very bad [22], polynomial complexity bounds (for the number of operations in in terms of the expected output size) exist for many important cases of interest. For example, for fixed , and using naive linear algebra on Macaulay matrices, one may show [21, 13, 14] that a sufficiently regular system of equations of degree can be solved in time . Here is the exponent of matrix multiplication [10]. For such a system, the Bezout bound for the number of solutions is reached, so the running time is polynomial in the expected output size . The implicit dependency of this bound on can be improved by using the “matrixF5” variant [1] of Faugère's F5 algorithm [7].
The F5 algorithm and all other currently known fast algorithms for Gröbner basis computations rely on linear algebra. At this point, one may wonder whether there is an intrinsic reason for this fact, or whether fast FFTbased arithmetic might be used to accelerate Gröbner basis computations. Instead of directly addressing this difficult problem, one may investigate whether such accelerations are possible for simpler problems in this area. One good candidate for such a problem is the reduction of a polynomial with respect to a fixed reduced Gröbner basis . In that case, the algebra is given once and for all, so it becomes a matter of precomputation to obtain and any other data that could be useful for efficient reductions modulo .
One step in this direction was made in [20]. Using relaxed multiplication [18], it was shown that the reduction of with respect to can be computed in quasilinear time in terms of the size of the equation . However, even in the case of bivariate polynomials, this is not necessarily optimal. In order to see the reason for this, consider , where is the ideal generated by two generic polynomials of total degree . Then , but the Gröbner basis for with respect the usual total degree ordering contains polynomials with coefficients. This means that we need space, merely to write down . One crucial prerequisite for even faster algorithms is therefore to design a terser representation for Gröbner bases.
The main aim of this paper is to show that it is actually possible to perform polynomial reductions in quasilinear time in some very specific cases. For simplicity, we will restrict our attention to bivariate polynomials and to ideals that satisfy suitable regularity conditions. Because of all these precautions, we do not expect our algorithms to be very useful for practical purposes, but rather regard our work as a “proof of concept” that quasilinear complexities are not deemed impossible to achieve in this context.
More precisely, with as above, our main results are as follows. We first introduce the concept of a “vanilla Gröbner basis” that captures the regularity assumptions that are needed for our algorithms. Modulo potentially expensive precomputations, we then present a more compact description of such a Gröbner basis that holds all necessary information in space. We next give an algorithm for reducing a bivariate polynomial of total degree with respect to in quasilinear time . In particular, multiplication in can be done in time , which is intrinsically quasioptimal. We also present an algorithm to convert between normal forms with respect to vanilla Gröbner bases for different monomial orderings. This algorithm is based on a Gröbner walk [5] with at most intermediate monomial orderings; its complexity is again quasioptimal.
It is instructive to compare these complexity bounds with the complexities of naive algorithms that are commonly implemented in computer algebra systems. For multiplications in , one may precompute the matrix that allows us to obtain the reduction of a product of two normal forms using a matrixvector product of cost . Since the product of two normal forms can be computed in quasilinear time , it follows that multiplications in take time . Similarly, changes of monomial orderings lead to matrices for representing the corresponding base changes. Naive conversions can then be performed in time .
As a final remark, we notice that the Kronecker solver [15] provides an alternative to Gröbner basis techniques for the resolution of polynomial systems and computations in quotient algebras . Such algorithms are often faster from a complexity point of view, but essentially only work for bases that correspond to lexicographical orders in the Gröbner basis setting.
Notations and terminology. We assume that the reader is familiar with the theory of Gröbner basis and refer to [11, 2] for basic expositions. We denote the set of monomials in variables by . A monomial ordering on is a total ordering that is compatible with multiplication. Given a polynomial in variables , its support is the set of monomials with . If , then admits a maximal element for that is called its leading monomial and that we denote by . If , then we say that is a term in . Given a tuple of polynomials in , we say that is reduced with respect to if contains no monomial that is a multiple of the leading monomial of one of the .
Unless stated otherwise, we will always work in the bivariate setting when , and use and as our main indeterminates instead of and . In particular, .
Consider a zerodimensional ideal of with Gröbner basis with respect to a given monomial ordering . We define the degree of to be the dimension of the quotient as a vector space. Our algorithms will only work for a special class of Gröbner bases with suitable regularity properties. For a generic ideal in the space of all zerodimensional ideals with fixed degree , we expect that these properties are always satisfied, although we have not proved this yet. For the time being, we define a vanilla Gröbner basis to be the Gröbner basis of an ideal of this type.
General monomial orderings that are suitable for Gröbner basis computations have been classified in [23]. For the purpose of this paper, it is convenient to restrict our attention to a specific type of bivariate monomial ordering that will allow us to explicitly describe certain Gröbner stairs and to explicitly compute certain dimensions.
We define the order to be the monomial order such that
Notice that corresponds to the usual total degree order.
Consider a zerodimensional ideal of of degree with Gröbner basis with respect to . Let be the set of monomials that are in normal form with respect to . In other words, corresponds to the set of monomials “under the Gröbner stairs”. For a sufficiently generic ideal of degree , we expect to consist exactly of the smallest elements of with respect to .
Figure 1 shows an example of a Gröbner basis whose leading monomials form a vanilla Gröbner stairs. We observe that the stair admits almost constant slope . In fact, the set can be described explicitly:

Then has elements and if we denote by the leading monomial of , we have (the elements being ordered such that , in particular the degrees are nonincreasing):
and .
For all , and .
For all , and .
Proof. We first notice that this sequence can indeed be the leading monomials for a reduced Gröbner basis, and that they are ordered as expected. Indeed, we have with , so that
In particular, this implies , whence or , so does not divide . For all other with , it is clear that does not divide . Moreover, , so that or and ; in both cases, . There are
Remark
The main reduction algorithm in this paper relies on a rewriting strategy that allows us to rewrite general linear combinations of elements in the Gröbner basis as linear combinations of fewer elements. In particular, it should be possible to express each as a linear combination of elements in a suitable subset of (this subset then generates the ideal ), with degrees that can be controlled.
It turns out that such a subset may need to contain three elements at least, but that generically works. In order to control the degrees in the linear combinations, we may also consider intermediate sets between and the full set , such as for various integer “step lengths” . This leads us to the following definition:
(1) 
We say that a family of polynomials is retractive for step length and degree if for all we can write
for some with .
Consider a Gröbner basis as in Proposition 3 and a linear combination with for all . Making rough estimates, the number of monomials in of degree is , whence the number of monomials of degree between and is bounded by . The set roughly corresponds to the set of monomials of degree , whence the support of contains at most monomials that are not in . Notice that such a combination is uniquely determined by its terms not in : if all the terms of are in , then by definition of a Gröbner basis.
On the other hand the polynomials with are determined by approximately coefficients. As soon as , it follows that
and it becomes likely that nontrivial relations of the type indeed exist. A refined analysis and practical experiments show that the precise threshold is located at , although we have no formal proof of this empirical fact.
We are now in a position to describe the class of Gröbner bases with enough regularity for our fast reduction algorithm to work.
the leading monomials of form a vanilla Gröbner stairs;
the family is retractive for step length and degree , for .
It appears that reduced Gröbner bases of sufficiently generic ideals are always of vanilla type, although we have not been able to prove this so far. We even do not know whether vanilla Gröbner bases exist for arbitrary fields (with sufficiently many elements) and degrees . Nevertheless, practical computer experiments suggest that sufficiently random ideals of degree admit Gröbner bases of this kind. More precisely, we have checked this (up to degrees in the range of a few hundreds) for ideals that are generated as follows by two random polynomials:
for , where and are random univariate polynomials of degrees and , and for any ordernig ;
for , where and are random bivariate polynomials of total degree (in this case the degree of the ideal is ), and for any ordering with ;
for , where and are random bivariate polynomials of degree in both variables (in this case the degree of the ideal is ), and for any ordering with .
In each of these cases, the threshold seems to be sharp. Nevertheless, for our complexity bounds, a threshold of the type would suffice, for any constant .
In this section, we quickly review some basic complexities for fundamental operations on polynomials over a field . Notice that results presented in this section are not specific to the bivariate case. Running times will always be measured in terms of the required number of field operations in .
We denote by the cost of multiplying two dense univariate polynomials of degree in . Over general fields, one may take [25, 24, 4]
In the case of fields of positive characteristic, one may even take , where denotes the iterated logarithm [16, 17]. We make the customary assumptions that is increasing and that , with the usual implications, such as .
For multivariate polynomials, the cost of multiplication depends on the geometry of the support. The multiplication of dense bivariate “block” polynomials in of degree in each variable can be reduced to multiplication of univariate polynomials of degree using the well known technique of Kronecker substitution [11]. More generally, for polynomials such that the support of the product of the support is included in an initial segment with elements, it is possible to compute the product in time . Here an initial segment of is a subset such that all divisors of any monomial are again in .
For the purpose of this paper, we need to consider dense polynomials in whose supports are contained in sets of the form . Modulo the change of variables , such a polynomial can be rewritten as , where the support of is an initial segment with the same size as . For a product of two polynomials of this type with a support of size , this means that the product can again be computed in time .
For the above polynomial multiplication algorithms, we assume that the input polynomials are entirely given from the outset. In specific settings, the input polynomials may be only partially known at some point, and it can be interesting to anticipate the computation of the partial output. This is particularly true when working with (truncated) formal power series instead of polynomials, where it is common that the coefficients are given as a stream.
In this socalled “relaxed (or online) computation model”, the coefficient of a product of two series must be output as soon as and are known. This model has the advantage that subsequent coefficients and are allowed to depend on the result . This often allows us to solve equations involving power series by rewriting them into recursive equations of the form , with the property that the coefficient only depends on earlier coefficients for all . For instance, in order to invert a power series of the form with , we may take . Similarly, if has characteristic zero, then the exponential of a power series with can be computed by taking .
From a complexity point of view, let denote the cost of the relaxed multiplication of two polynomials of degree . The relaxed model prevents us from directly using fast “zealous” multiplication algorithms from the previous section that are typically based on FFTmultiplication. Fortunately, it was shown in [18, 9] that
(2) 
This relaxed multiplication algorithm admits the advantage that it may use any zealous multiplication as a black box. Through the direct use of FFTbased techniques, the following bound has also been established in [19]:
In the sequel, we will only use a suitable multivariate generalization of the algorithm from [18, 9], so we will always assume that is of the form (2). In particular, we have .
Let us now consider a Gröbner basis of an ideal in , or, more generally, an autoreduced tuple of polynomials in . Then for any , we may compute a relation
such that is reduced with respect to . We call an extended reduction of with respect to .
The computation of such an extended reduction is a good example of a problem that can be solved efficiently using relaxed multiplication and recursive equations. For a multivariate polynomial with dense support of any of the types discussed in section 3.1 , let denote a bound for the size of its support. With as in ( 2 ), it has been shown
1. The results from [20] actually apply for more general types of supports, but this will not be needed in this paper.
(3) 
This implies in particular that the extended reduction can be computed in quasilinear time in the size of the equation . However, as pointed out in the introduction, this equation is in general much larger than the input polynomial .
Extended reductions are far from being unique (only is unique, and only if is a Gröbner basis). The algorithm from [20] for the computation of an extended reduction relies on a selection strategy that selects a particular index for every monomial such that is nonempty. The initial formulation [20] used the simplest such strategy by taking , but the complexity bound (3) holds for any selection strategy. Now the total size of all quotients may be much larger than the size of for a general selection strategy. One of the key ingredients of the fast reduction algorithm in this paper is the careful design of a “dichotomic selection strategy” that enables us to control the degrees of the quotients.
Remark
Let be a vanilla Gröbner basis of some ideal with respect to and assume the notations from Proposition 3. We recall from the introduction that a major obstruction for the design of reduction algorithms that run in quasilinear time is that it requires space to explicitly write down the full basis . The aim of this section is to introduce a suitable “terse representation” that can be stored in space , but that still contains all necessary information for efficient computations modulo .
For each , let be as in (1). Also, for , let be a shorthand for . Since is a vanilla Gröbner basis, Definition 6 ensures in particular the existence of coefficients for , , and , such that
We call these the retraction coefficients for . For each given , the computation of the retraction coefficients reduces to a linear system of size with (for the image space, consider the basis ), which is easily solved by Gaussian elimination. Notice that the space needed to write the retraction coefficients is much smaller than the Gröbner basis:
Proof. For every , there are indices in , and we notice that . For any given , the retraction coefficients involve at most indices and indices , whence at most pairs . Since the support of has size , it follows that all retraction coefficient together require space
We observe that the space needed to write all relations is about the same size as the dimension of the quotient algebra , up to a logarithmic factor.
For vanilla Gröbner bases, it is a priori possible to recover from using the retraction coefficients: with , first compute , next and , and so on. In order to compute reductions of the form efficiently, we will need slightly more information. In particular, we wish to access some of the head terms of the . More precisely, if the quotient has degree , then we need to know the terms of with degree at least in order to compute the quotient using a relaxed reduction algorithm.
all terms of of degree less than are zero;
all terms of of degree at least are equal to the corresponding terms in .
Notice that this upper truncation can be written using space . For the reduction strategy that we plan to use, we will have
(4) 
for all , where denotes the adic valuation of . This motivates the following definition:
the sequence of truncated elements , where
for ;
is the upper truncation of at precision for all other ;
the collection of all retraction coefficients as in section 4.1.
Let be a vanilla Gröbner basis for an ideal as in the previous section and assume that its terse representation has been precomputed. The goal of this section is to present our main algorithm that computes the extended reduction of a polynomial of degree in quasilinear time . This is quasioptimal with respect to the dimension of the quotient algebra and the size of the support .
The reduction algorithm proceeds in two steps: in a first stage, we compute the quotients ; we next evaluate the remainder by rewriting the linear combination using fewer and fewer terms.
To compute the quotients, we reduce as in section 3.3 against the tuple , in such a way that the degrees of the quotients are bounded as in equation (4). This is done using the algorithm from [20], but with the following dichotomic selection strategy. Given a monomial , we reduce against , where is determined as follows:
if divides , then take ;
else if divides , then take ;
else we take to be the unique element in with .
This selection strategy is illustrated in Figure 2 .
Figure 2. The dichotomic selection strategy: monomials falling in each area are reduced against the corresponding basis element. 
holds for all , so that , and the extended reduction can be computed in time
Proof. Let with , so that for , and denote . Then we observe that : if not, then would divide , whereas . A similar reasoning with (or , whenever ) shows that . It follows that .
This also proves that and , for any . Since the number of indices with is bounded by , we get
The next important observation is that the quotients obtained in the above way can actually be used as quotients for the extended reduction of with respect to :
Then is reduced with respect to .
Once the quotients are known, we need to compute the remainder . We do this by rewriting (or retracting) the linear combination into a linear combination using the following algorithm:
Algorithm
For , define , and return
Proof. By construction, we notice that if and (that is ). Let us now show by induction over that
This is clearly true for . We have
which proves the correctness of Algorithm 1. Again by induction over , it is not hard to see that, for , the bound implies
(5) 
Combining our subalgorithms, we obtain our algorithm for extended reduction.
Algorithm
Input: A tersely represented vanilla Gröbner basis and
Output: An extended reduction of modulo
Compute the extended reduction with respect to
Compute as a function of using Algorithm 1
Compute
Return .
Proof. Because of Lemma 12, the extended reduction with respect to is computed in time
Proposition 13 ensures that the quotients are also valid with respect to . The next step is to evaluate the remainder . The 's are computed in time using Lemma 14 and we have
For , it follows from (5) that . Consequently, the evaluation of takes time
Let be a vanilla Gröbner basis for an ideal with respect to and assume that we we have precomputed a terse representation for . Elements in the quotient algebra can naturally be represented as polynomials in that are reduced with respect to . An immediate application of Theorem 15 is a multiplication algorithm for that runs in quasilinear time.
More precisely, with the notations from Proposition 3, given two polynomials that are reduced with respect to , we have and , whence and . It follows that can be computed in time , whereas the reduction of with respect to takes time . This yields:
Let us now assume that our ideal admits a vanilla Gröbner basis with respect to the ordering for all . We will write for the quotient algebra when representing elements using normal forms with respect to . If , then we notice that is also a Gröbner basis with respect to the lexicographical monomial ordering . In order to efficiently convert between and with , we first consider the case when :
Proof. Assume that has elements and has elements . We know from Proposition 3 that and similarly . Now given that is reduced with respect to , we have , whence and . Theorem 15 therefore implies that normal form of w.r.t. can be computed in time
For general , let be such that and . Then we may perform conversions between and using a Gröbner walk
More precisely:
As explained in the introduction, we deliberately chose to present our results in the simplest possible setting. As a future work, it would be interesting to generalize our algorithms. The following two extensions should be rather straightforward:
The consideration of general monomial orderings, starting with for .
Generalizations to multivariate polynomials in . We expect no essential problems for fixed . However, the dependence of the complexity on is likely to be polynomial in .
Some of the more challenging problems are as follows:
Is it true that a “sufficiently generic” zerodimensional ideal of fixed degree necessarily admits a vanilla Gröbner basis?
Given a vanilla Gröbner basis, what is the actual complexity of computing its terse representation? Our first analysis suggest a bound , but we suspect that the computation of the retraction coefficients can be accelerated by using the sygyzies that result from reducing the polynomials of basis elements to zero.
Can our results be generalized to the degenerate case of nonvanilla Gröbner bases ?
On the long run, one might also wonder whether some of the new techniques can be used for the efficient computation of Gröbner bases themselves. For the moment, this seems far beyond reach. Nevertheless, a quasioptimal algorithm does exist for the particular case of an ideal generated by two generic polynomials of total degree , when working with respect to the monomial ordering . We intend to report on the details in a forthcoming paper.
[1] Magali Bardet, JeanCharles Faugère, and Bruno Salvy. On the complexity of the F5 Gröbner basis algorithm. Journal of Symbolic Computation, pages 1–24, sep 2014.
[2] Thomas Becker and Volker Weispfenning. Gröbner bases: a computational approach to commutative algebra, volume 141 of Graduate Texts in Mathematics. SpringerVerlag, New York, 1993.
[3] Bruno Buchberger. Ein Algorithmus zum Auffinden der Basiselemente des Restklassenrings nach einem nulldimensionalen Polynomideal. PhD thesis, Universitat Innsbruck, Austria, 1965.
[4] David G Cantor and Erich Kaltofen. On fast multiplication of polynomials over arbitrary algebras. Acta Informatica, 28(7):693–701, 1991.
[5] Stéphane Collart, Michael Kalkbrener, and Daniel Mall. Converting bases with the gröbner walk. Journal of Symbolic Computation, 24(34):465–469, 1997.
[6] JeanCharles Faugère. A new efficient algorithm for computing Gröbner bases (F4). Journal of Pure and Applied Algebra, 139(1–3):61–88, 1999.
[7] JeanCharles Faugère. A new efficient algorithm for computing Gröbner bases without reduction to zero (F5). In Proceedings of the 2002 international symposium on Symbolic and algebraic computation, ISSAC '02, pages 75–83. New York, NY, USA, 2002. ACM.
[8] JeanCharles Faugere, Patrizia Gianni, Daniel Lazard, and Teo Mora. Efficient computation of zerodimensional Gröbner bases by change of ordering. Journal of Symbolic Computation, 16(4):329–344, 1993.
[9] M. J. Fischer and L. J. Stockmeyer. Fast online integer multiplication. Proc. 5th ACM Symposium on Theory of Computing, 9:67–72, 1974.
[10] F. Le Gall. Powers of tensors and fast matrix multiplication. In Proc. ISSAC 2014, pages 296–303. Kobe, Japan, July 23–25 2014.
[11] J. von zur Gathen and J. Gerhard. Modern Computer Algebra. Cambridge University Press, 3rd edition, 2013.
[12] Vladimir P. Gerdt and Yuri A. Blinkov. Involutive bases of polynomial ideals. Mathematics and Computers in Simulation, 45(5):519–541, 1998.
[13] M. Giusti. Some effectivity problems in polynomial ideal theory. In Proc. Eurosam '84, volume 174 of Lecture Notes in Computer Science, pages 159–171. Cambridge, 1984. Springer, Berlin.
[14] M. Giusti. A note on the complexity of constructing standard bases. In Proc. Eurocal '85, volume 204 of Lecture Notes in Computer Science, pages 411–412. SpringerVerlag, 1985.
[15] M. Giusti, G. Lecerf, and B. Salvy. A Gröbner free alternative for polynomial system solving. Journal of Complexity, 17(1):154–211, 2001.
[16] D. Harvey and J. van der Hoeven. Faster integer and polynomial multiplication using cyclotomic coefficient rings. Technical Report, ArXiv, 2017. http://arxiv.org/abs/1712.03693.
[17] D. Harvey, J. van der Hoeven, and G. Lecerf. Faster polynomial multiplication over finite fields. J. ACM, 63(6), 2017. Article 52.
[18] J. van der Hoeven. Relax, but don't be too lazy. JSC, 34:479–542, 2002.
[19] J. van der Hoeven. Faster relaxed multiplication. In Proc. ISSAC '14, pages 405–412. Kobe, Japan, July 2014.
[20] J. van der Hoeven. On the complexity of polynomial reduction. In I. Kotsireas and E. MartínezMoro, editors, Proc. Applications of Computer Algebra 2015, volume 198 of Springer Proceedings in Mathematics and Statistics, pages 447–458. Cham, 2015. Springer.
[21] D. Lazard. Gröbner bases, gaussian elimination and resolution of systems of algebraic equations. In J. A. van Hulzen, editor, Proc. EUROCAL'83, number 162 in Lect. Notes in Computer Sc., pages 146–156. Springer Berlin Heidelberg, 1983.
[22] Ernst Mayr. Membership in polynomial ideals over q is exponential space complete. STACS 89, pages 400–406, 1989.
[23] L. Robbiano. Term orderings on the polynominal ring. In European Conference on Computer Algebra (2), pages 513–517. 1985.
[24] A. Schönhage. Schnelle Multiplikation von Polynomen über Körpern der Charakteristik 2. Acta Infor., 7:395–398, 1977.
[25] A. Schönhage and V. Strassen. Schnelle Multiplikation großer Zahlen. Computing, 7:281–292, 1971.