Given t bivariate polynomials f1, . . . , ft ∈ K[x, y], and an integer k we report a work-in-progress to compute a minimal, not reduced, lexicographic Gröbner basis of the ideal ⟨f1, . . . , ft, xk⟩ in O∼(td2k), where d is an upper bound on the y-degree of the fi's. Using the fast normal form algorithm of Schost & St-Pierre [1], this implies that we can compute its reduced Gröbner basis in O∼(td2k + s2dk) where s is the number of polynomials contained in the output Gröbner basis. In many instances this improves the algorithm of Schost & St-Pierre [2] based on the Howell matrix normal form that runs in time O∼(tdωk).
order with x ≺ y. Under our setting we have hs = P k, and if we let degx(P ) = 1 like when P = x, then degx(hs) = k. Let degy(h0) = n0 be the largest y-degree of the polynomials in H, and let s + 1 = |H| be the number of polynomials in the output. Then reducing H costs O∼(s2n0k) (see [1, Prop. 4.4 & Prop. 5.1]).
Note that s ≤ min{k, d} and n0 ≤ d. So we obtain an algorithm that computes the reduced
lexGb in O∼(td2k + s2n0k), always within O∼(td2k + s2dk). This is comparable or better than
O∼(tdωk) as soon as s2n0 = O(tdω). In the case t = O(1) and s ≈ d = k, we obtain O∼(d4)
which is worth than O∼(dω+1). But in many cases, the asymptotic complexity is better.
Implementation The articles [
On the other hand, since the presented algorithm that computes a minimal non-reduced lexGb in O∼(td2k) can be compared to the quadratic-time standard Euclidean algorithm, it is ecfiient up to fast univariate arithmetic (polynomial operations involving the x-variable only). Our implementation in Magma (available at http://xdahan.sakura.ne.jp/lexgb24.html) supports this claim. As for the normal form algorithm modulo a reduced Gröbner basis of Schost & St-Pierre [1, Section 4], making an implementation eficient is an interesting challenge. For now we resorted here to the internal Magma command “ Reduce” (in orange).
Some timings
We tested the algorithm for two input polynomials modulo xk:
ak ≡
k !
Y(y + i + x + · · · + xi) , bk ≡ (y + 1 + 2x)
i=1
k
Y(y + i + x + · · · + xi−1 + 2xi)
i=2
!
The reduced lexGb of ⟨ak, bk, xk⟩ has s + 1 = k + 1 polynomials (the maximum possible) and is
dense (it has O(k3) coeficients). Therefore, this family of examples is suitable for benchmarking
as it involves worst case situations: the number of recursive calls is maximal, the cost of the
normal form is maximal. Note also that taking only t = 2 polynomials as input is not restrictive
since recursive calls involve more polynomials in the input. We report below on timings for
k = 30, 40, . . . , 120 (left) and k = 70, 140, . . . , 250 (right) over a prime finite field of 64bits. With
t = O(1), k ≈ d, the theoretical cost to obtain a minimal lexGb is O∼(k3). The internal command
Reduce of Magma becomes quickly the bottleneck (in orange. Time > 500s for k > 200, timings
are not displayed). Without surprise, its timing grows faster than the cost of the fast version
of Schost & St-Pierre, which is here O∼(k4) (it seems to be closer to something in O∼(k5)).
Although we could not compare with the Howell form approach of [
Scope The motivation behind working modulo P k is twofold. Firstly, this serves as a skeleton for
a similar algorithm that tackles the more general input ⟨f1, . . . , ft, T ⟩ for an arbitrary polynomial
T ∈ K[x], not necessarily the power of an irreducible one. See [
Treating only two variables is clearly limited. Yet, all aspects shall be mastered as there
is a clif in dificulty when considering more than two variables: no general form of Lazard’s
structural theorem [
Related works Recently, articles dealing with bivariate Gröbner bases have flourished. A
number of them address the question of quasi-optimal asymptotic complexity estimates, with
adequate genericity assumptions, and the relation with the resultant [
Overview It is based on ideas introduced in [
Cf = gcd(content(f˜), P k) ∈ K[x], f is monic in y, ⟨f˜, P k⟩ = ⟨Cf f, P k⟩.
(1) The Euclidean algorithm can be pursued with the monic f , and Cf f will be part of the lexGb.
We adapt this strategy to design the main algorithm H ← Add(f, G) where G is a minimal lexGb such that G ∩ K[x] = ⟨P k′ ⟩ with k′ ≤ k, f ∈ K[x, y] and H is a minimal lexGb of ⟨f ⟩ + ⟨G⟩. Assuming for the moment this algorithm correct and running in time O∼(d2k′), the general algorithm 1 “ lexGb” has the following worst-case complexity:
Input: Bivariate polynomials f1, . . . , ft. Power of an irreducible polynomial P k ∈ K[x].
Output: reduced lexGb of ⟨f1, . . . , ft, P k⟩
Input: g ∈ K[x, y], G = [g0, . . . , gs] minimal lexGb modulo P k = gs
Output: minimal lexGb of ⟨g⟩ + ⟨G⟩
6 if G == [constant] then
7 return [
Algorithms AddTwoA and AddTwoB The input are monic bivariate polynomials a, b, monic univariate polynomials Ca, Cb which are powers of P , and a minimal lexGb G modulo P k.
Input: f ∈ K[x, y] monic degy(f ) ≥ 1, Cf = P t ∈ K[x], G minimal lexGb modulo P k Output: minimal lexGb of ⟨Cf f ⟩ + ⟨G⟩ Additional degree constraints on a, b, Ca, Cb depend on one or the other algorithm. The output is a minimal lexGb of ⟨Ca a, Cb b⟩ + ⟨G⟩ (whence the name “ AddTwo”). The key point is the degree decrease obtained by the Euclidean division at Lines 24 and 34. Then they undertake recursive calls. These divisions henceforth imply the complexity stated in Theorem 1.
Input: 1. a, b ∈ K[x, y] monic, degy(a) > degy(b) 2. Ca, Cb ∈ K[x] powers of P , Ca | Cb | P k, 3. G minimal lexGb modulo P k, and degy(a) > degy(G) Output: minimal lexGb of ⟨Ca a, Cb b⟩ + ⟨G⟩
G′ ← Add(r, C1b G)
G′′ ← Add(b, G′) 24 r ← a mod b // b monic. Over R = K[x]/⟨ PCkb ⟩. It holds ⟨Cb a, Cb b, P k⟩ = ⟨Cb b, Cb r, P k⟩ 25 if r ≡ 0 mod Cg1b then // Here ⟨Cb a, Cb b, P k⟩ = ⟨Cb b, P k⟩ 26 G′′ ← Add(b, C1b G) // Here ⟨Cb G′′⟩ = ⟨Cb b⟩ + ⟨G⟩ 27 else 28 29 // ⟨CbG′⟩ = ⟨Cb r⟩ + ⟨G⟩ // ⟨CbG′′⟩ = ⟨Cb b⟩ + ⟨CbG′⟩ = ⟨Cb b, Cb r⟩ + ⟨G⟩ = ⟨Cb b, Cb a⟩ + ⟨G⟩ 30 if Ca == Cb then 31 return Cb · G′′ 32 else 33 return [Ca a] cat Cb · G′′ // Here ⟨CbG′′⟩ = ⟨Cb b, Ca a⟩ + ⟨G⟩ // output generates ⟨Ca a⟩ + ⟨CbG′′⟩ = ⟨Ca a, Cb b⟩ + ⟨G⟩
Input: 1. a, b ∈ K[x, y] monic, degy(a) ≤ degy(b), 2. Ca, Cb ∈ K[x] powers of P , Ca | Cb | P k, 3. G minimal lexGb modulo P k, degy(b) > degy(G)
Output: minimal lexGb of ⟨Ca a, Cb b⟩ + ⟨G⟩ 34 r ← CCab b mod a // a monic. Over R = K[x]/⟨ PCak ⟩. It holds ⟨Ca r, Ca a, P k⟩ = ⟨Cb b, Ca a, P k⟩. 35 if r ≡ 0 mod PCak then // Here ⟨Ca a, P k⟩ = ⟨Ca a, Cb b, P k⟩ 36 return Ca · Add(a, C1a G) // Output generates ⟨Ca a⟩ + ⟨G⟩ 37 else 38
G′ ← Add(r, C1a G) // ⟨CaG′⟩ = ⟨Ca r⟩ + ⟨G⟩ return Ca · Add(a, G′) // Output generates ⟨Ca a⟩ + ⟨CaG′⟩ = ⟨Ca a, Cb b⟩ + ⟨G⟩