Backward error analysis of approximate Grbner basis
Kosaku Nagasaka
Kobe University ∗E-mail:nagasaka@main.h.kobe-u.ac.jp

Abstract
Computing a Gröbner basis for the given polynomial system with inexact (erroneous)coeﬃcients is one of the challenging problems in symbolic-numeric computations and there
are several approaches to ﬁnd an approximate Gröbner basis that are usually computedby ﬂoating-point numbers. However, in general the resulting basis is not a Gröbner basis
and does not generate the given ideal. This is the problem of all kinds of approximateGröbner bases even though there are some workarounds (with concepts of approximate
basis, ideal and so on). In this paper, we introduce a proof of concept method and open
questions to ﬁnd an exact result from those approximate Gröbner bases, that is a Gröbner
basis of the ideal generated by a nearby polynomial set in the exact sense.
Key words: Gröbner Bases, Symbolic-Numeric Computations, Inexact

1

Introduction

For the given ideal with a ﬁnite set of polynomials, computing its Gröbner basis can be doneby the well known Buchberger’s algorithm and this basis is very useful (see the graduate text
book [1] for example). However, in practical situations, the given polynomials with empirical
data on their coeﬃcients may have a priori errors and the conventional algorithms can notwork in general. This is the problem so called “approximate Gröbner basis” which has beenstudied in the past several decades and is one of the challenging problems in symbolic-numericcomputations.
In Sasaki and Kako [17], this problem is classiﬁed into the ﬁrst and second kinds of problem.
The ﬁrst kind is computing a Gröbner basis for the ideal generated by the given polynomials
with exact coeﬃcients by numerical arithmetic (e.g. ﬂoating-point arithmetic). The second
kind is for the given polynomials with inexact coeﬃcients having a priori errors. In this case,
we have to operate with a priori errors whether we compute a basis by exact arithmetic or not.
For the ﬁrst kind, Shirayanagi [19, 20] proposed algorithms using stabilization techniques[21] by which we can compute a numerical sequence of Gröbner bases with exact inputs andthe sequence converges to the exact result. By this, we can recover the exact coeﬃcients∗

3-11 Tsurukabuto, Nada-ku, Kobe 657-8501 JAPAN.

1

from the resulting numerical coeﬃcients by just rationalizing them since the upper bounds ofcomputational cost and space are computable and theoretically ﬁnite. Therefore, for the ﬁrst
kind, ﬁnding exact result from approximate Gröbner basis is not the problem (see the example
in [13]).
For the second kind, there are several studies ([22, 24, 10, 18, 15, 3] and citations therein)from the numerical point of view. In this case, it is diﬃcult to ﬁnd exact result from approximate Gröbner basis since the correct input (set of polynomials) is unknown. In contrast,computing a comprehensive Gröbner system [25] for polynomials with parameters instead of
inexact coeﬃcients is an approach [26] using exact arithmetic hence we do not have to recoverany exact result (it’s already in the exact representation). However, in general, a comprehensiveGröbner system has a huge number of segments and its computation time is slow though there
are several improvements (see [9] and citations therein). This is a reason that approximateGröbner basis is still challenging and there are studies using ﬂoating-point arithmetic.

1.1

The Problem to be Solved

Computing approximate Gröbner basis can be thought as just one of symbolic-numeric computations for polynomials (see [16] for some note from the methological point of view): approximate polynomial GCD, approximate factorization and so on. However, there is a big diﬀerence
between approximate Gröbner basis and others that the backward error analyses are naturally
given or not (i.e. easy or not).
For example, we consider an approximate GCD of the following f˜(x) and g̃(x) by thealgorithm proposed in [8].
f˜(x) = 54x6 − 36x5 − 192x4 + 42x3 + 76x2 − 62x + 15,g̃(x) = 73x5 + 36x4 − 103x3 − 70x2 − 48x + 35.
In this case, we have an approximate common divisor h̃(x) = 1.00x2 +0.99x−0.55 with tolerance
ε = 10−8 :f˜(x) ≈ h̃(x)(54.34x4 − 90.20x3 − 72.20x2 + 63.65x − 27.07),g̃(x) ≈ h̃(x)(72.84x3 − 36.20x2 − 26.83x − 63.33).
The resulting approximate common divisor h̃(x) can be characterized as the polynomial GCDof the following polynomials in the exact sense, by rationalizing the coeﬃcients.
f (x) = 2717
x6 − 182017
x5 − 38277
x4 + 20891
x3 + 151307
x2 − 154517
x + 29777
,
50
5000
200
500
2000
2500
2000
g(x) = 1821
x5 + 2011985808912
x4 − 10273
x3 − 657655415835
x2 − 239701
x + 69663.
25
56026069819
100
9397534153
5000
2000
Moreover, we consider an approximate factorization of the following polynomial (from theexample in [7]).
3f˜(x, y, z) = 81x4 + 72x2 y 2 + 1292
x2 z 2 − 648x2 + 16y 4
1 2 2
3 2
+ 969
y z − 288y 2 − 837227
z 4 − 323
z + 1296.
1292

2

In this case, we have the following approximate factorization f˜1 (x, y, z)f˜2 (x, y, z) with tolerance
ε = 4.54478 × 10−6 .
f˜1 (x, y, z) = 9.000x2 + 4.000y 2 − 25.46z 2 − 36.00,
f˜2 (x, y, z) = 9.000x2 + 4.000y 2 + 25.46z 2 − 36.00.
The resulting approximate factorization f˜1 (x, y, z)f˜2 (x, y, z) can be characterized as the factorization of the following polynomial in the exact sense, by rationalizing the coeﬃcients.
f (x, y, z) = 81x4 + 72x2 y 2 − 648x2 + 16y 4 − 288y 2 − 78400
z 4 + 1296.
121
In contrast, approximate Gröbner basis does not have this behavior in general. To see
this, we consider an approximate Gröbner basis of the ideal generated by the following set ofpolynomials F̃app by Mathematica [12], and G̃app is the resulting approximate Gröbner basis
w.r.t. the graded lexicographic order (x  y).
F̃app = {0.01084x3 y + 0.891x3 , 0.503xy 3 + 0.1129x + 0.02201},G̃app = {1.0xy 3 + 0.224453x + 0.0437575, 1.0x3 − 7.87965 × 10−8 x2 }.
However, we have the following result if we compute a Gröbner basis of the ideal generated byG̃app with the rationalized coeﬃcients in the exact sense (we show only ﬁrst 6 decimal places
to save the paper space instead of full rational representations).
Gapp ≈ {1.23120 × 1030 y 3 + 6.83710 × 1035 , 3.12500 × 1021 x − 2.46239 × 1014 }.
Moreover, the following Gex is a Gröbner basis of the ideal generated by F̃app with the rationalized coeﬃcients, which is diﬀerent from Gapp and G̃app (only ﬁrst 6 decimal places insteadof full rational representations). Note that we consider the second kind of problem hence ingeneral the resulting Gex is not the basis we want (for details, see [15] and [16]).
Gex ≈ {5.55931 × 1017 x − 4.38054 × 1010 , 271.000y + 22275.0}.
Therefore, the resulting approximate Gröbner basis is not a Gröbner basis and does not generate the given ideal in the exact sense. This behavior is common for algorithms computing
approximate Gröbner basis hence we have a very natural question: “What is that we computed?” This is the problem of all kinds of approximate Gröbner bases even though there aresome workarounds (with concepts of approximate basis, ideal and so on). In this paper, we
introduce a proof of concept method and open questions to ﬁnd an exact result from those approximate Gröbner bases, that is a Gröbner basis of the ideal generated by a nearby polynomial
set in the exact sense (so we can have a backward error analysis).
At ﬁrst we introduce the notations we use and the basic structure of our method in thenext section 2. In the section 3, we discuss about a nearby Gröbner basis for the resulting
approximate Gröbner basis for which we consider a nearby polynomial system generating its
sub-ideal in the section 4. In general, the resulting nearby polynomial system does not generate
the ideal generated by the nearby Gröbner basis. We give some results on this problem in thesection 5. Finally, in the section 6, we give some remarks and open questions for further work.
3

2

Preliminary Discussion

We always assume that we have F̃app = {f˜1 , . . . , f˜n } ∈ F[~x] = F[x1 , . . . , x` ] and G̃app ={g̃1 , . . . , g̃m } ∈ F[~x] as the given polynomial system in variables ~x = x1 , . . . , x` with inexact
coeﬃcients and its (minimal and approximate/numerical) Gröbner basis w.r.t. the term order≺, respectively, where F is the set of ﬂoating-point numbers hence F ⊂ R (the real number
ﬁeld but note that F is not a ﬁeld). Note that we discuss about polynomials over R however it
is easy to extend them to polynomials over C (but we restrict to over R for simplicity’s sake).
Though there are several deﬁnitions of approximate Gröbner basis, we just assume that itis minimal (in the ordinary sense) hence for all g̃ ∈ G̃app we have ∀h̃ ∈ G̃app \ {g̃}, ht(h̃) - ht(g̃)
where ht(f ) denotes the head term of polynomial f (~x) w.r.t. the term order. Note that “term”
means a power product of variables and “monomial” means a term with a coeﬃcient. In thispaper, we always represent a numerical object of some mathematical object with the tilde
symbol: ˜· hence ã is over F and a is over R. We consider the following problem.
Problem 1 [Nearby Gröbner basis and system] For the given F̃app , G̃app ⊂ F[~x], compute
Fcl , Gcl ⊂ R[~x] such that Gcl is a Gröbner basis of ideal(Fcl ) in the exact sense and Fcl and Gcl
are close to F̃app and G̃app , respectively.
/
For this problem we propose the following 3 steps:
1. Compute a close enough exact Gröbner basis Gcl of its self to the given approximateGröbner basis G̃app (discussed in the section 3).
2. Compute a close enough system Fcl0 that is a subset of the ideal generated by the resulting
exact Gröbner basis Gcl (discussed in the section 4). This can be combined with the above.
3. Compute a close enough system Fcl whose Gröbner basis is the resulting exact Gröbner
basis Gcl (discussed in the section 5).
Moreover, we use the following notations. By hc(f ) we denote a coeﬃcient of head monomialof f (~x). For a set of polynomials F , we denotes the set of head terms of elements in F by ht(F ).
For a polynomial f (~x) we denote the set of terms of monomials with non-zero coeﬃcients inf (~x) by supp(f ). We denote the S-polynomial of f (~x) and g(~x) by Spoly(f, g) and the normalG
form of f (~x) w.r.t. G by f (~x) . For a polynomial f (~x), we denote the dense coeﬃcient vector−−→−→of f (~x) w.r.t. the term order by f (~x) or just f .

3

Nearby Gröbner BasisIn this section, we consider the following sub-problem.
Problem 2 [Nearby Gröbner basis of its self]
For the given G̃app ⊂ F[~x], compute Gcl ⊂ R[~x] such that Gcl is a Gröbner basis of ideal(Gcl )in the exact sense and Gcl is close to G̃app .
/4

We formalize the problem as follows. For each g̃i ∈ G̃app , let gi (~x) be a parametric polynomial over R[~p] such that∑gi (~x) =pij tj ∈ R[~p][~x](3.1)
tj ∈supp(g̃)

and put Gpar = {g1 , . . . , gm }, the set of polynomials gi (~x). The problem is solved if we canﬁnd a specialization S : R[~p] → R such that S(Gpar ) is a Gröbner basis of its self and close
to G̃app . For this computation, we can use the algorithms for Comprehensive Gröbner System(see [9] and citations therein). However, computing a comprehensive Gröbner system of Gpar
is too much for our purpose since we only need a one branch (the resulting basis is the given
set of polynomials). The following trivial lemma makes the problem easier to solve under ourassumptions.
Lemma 1 (Existence of a nearby basis)
For any G̃app ⊂ F[~x], there always exists Gcl ⊂ R[~x].

/Proof By the assumption, G̃app is minimal (though it may not be a Gröbner basis) henceht(G̃app ) is a Gröbner basis of its self.
By this trivial lemma, we focus to compute a close Gröbner basis with the same head terms
as those of G̃app . This is reasonable since the head terms play the essential role in the Gröbner
basis theory hence any approximate Gröbner basis may (or should) take care of them. With
this restriction the problem is similar to the inverse Gröbner basis problem [23], however, ourinput is not a monomial ideal and we have to minimize the diﬀerence from the given basis.
Therefore, the problem is equivalent to an optimization problem:∑mminimizex) − g̃i (~x)ki=1 kgi (~
p
~
(3.2)
Gpar
subject to ht(gi ) = ht(g̃i ) and Spoly(gi , gj )=0
where k · k is the Euclidean norm (but not limited to this norm). Moreover, we can convert
Gpar
Spoly(gi , gj )= 0 into polynomial constraints in p~ since we can put hc(gi ) = 1 by theassumption ht(gi ) = ht(g̃∑mi ) hence any monomial reductions can be done over R[~p]. In this case,
we have to minimize i=1 kpi1 × gi (~x) − g̃i (~x)k instead.
This optimization problem can be solved by the well known method of Lagrange multipliersor cylindrical algebraic decomposition since the problem 2 does not require the optimum Gcl
but only close to G̃app .
Example 1 [Nearby Gröbner basis of its self]
We compute Gcl for the approximate Gröbner basis G̃app = {1.0xy 3 +0.224453x+0.0437575, 1.0x3 −7.87965×10−8 x2 } given in the section 1.1. At ﬁrst, we construct a set of parametric polynomials:
Gpar = {g1 (~x) = xy 3 + p12 x + p13 , g2 (~x) = x3 + p22 x2 }.
The corresponding polynomial constraints are computed as
Gpar

Spoly(g1 , g2 ) = −p22 x2 y 3 + p12 x3 + p13 x2 =⇒ Spoly(g1 , g2 )5

= p13 x2 + p13 p22 x.

Therefore, we solve the optimization problem:
minimize(p11 ,p12 ,p13 ,p21 ,p22 )kp11 g1 − g˜1 k + kp21 g2 − g˜2 ksubject to p13 = 0 and p13 p22 = 0.
The target function has an optimum at
p11 = 1, p12 =1122266401590457
246239085291621, p13 = 0, p21 = 1, p22 = −.
5000000000000000
3125000000000000000000

Finally, we have the following solution for the problem 2.
246239085291621
Gcl ={xy 3 + 1122266401590457
x, x3 − 3125000000000000000000
x2 }5000000000000000≈{xy 3 + 0.224453x, x3 − 7.87965 × 10−8 x2 }.
/In this subsection, we parameterized the given polynomials as in the equation (3.1) hence
implicitly we restricted the support of parametric polynomial to that of the given polynomial.
In general, we have to assume that the parameterized polynomial gi (~x) has all the possible
terms but the number of such terms may be inﬁnite (e.g. the lexicographic order). The aim of
this paper is answering to the natural question: “What is that we computed?” so our implicit
assumption in the equation (3.1) is acceptable (or required).
We note that in our preliminary implementation on Mathematica we use the built-in function: FindInstance with NMinimize for simplicity’s sake since the method of Lagrange multipliers is not practical. We just ﬁnd a numerical local optimum and ﬁnd exact values satisfying
the constraints near the numerical optimum.

4

Nearby Polynomial System

In this section, we consider the following sub-problem.
Problem 3 [Nearby polynomial system]
For the given F̃app ⊂ F[~x] and Gcl ⊂ R[~x], compute Fcl0 ⊂ R[~x] generated by ideal(Gcl ) in theexact sense and Fcl0 is close to F̃app .
/This is equivalent to ﬁnd the polynomials hij ∈ R[~x]:fi (~x) =m∑hij (~x)gj (~x) (i = 1, . . . , n)

(4.1)

j=1

∑
satisfying ni=1 kfi (~x) − f˜i (~x)k is small. As in the implicit assumption of the equation (3.1), we
need a discussion for the supports of polynomials fi (~x). The supports of f˜i (~x) are not reliable
since F̃app is the given polynomial system with inexact coeﬃcients. The reliable information we
have is only the given Gcl since this is over R and is a Gröbner basis of its self in the exact sense.
6

Hence we assume that the support of fi (~x) is the union of supp(h̃ij (~x)gj (~x)) and supp(ri (~x))
over R[a, b] satisfying
f˜i0 (~x) =m∑h̃ij (~x)gj (~x) + r̃i (~x), r̃i (~x) ≺ g1 (~x), . . . , gn (~x)

j=1∑where f˜i0 (~x) = af˜i (~x) + b tjk × gj (~x) ∈ R[a, b][~x] and the condition of the sum is supp(tjk ×
gj (~x)) ∩ supp(f˜i (~x)) 6= φ for any term tjk in R[~x].
Therefore, the problem 2 under this assumption is equivalent to the following least square
problem over R.
→
→ −
−
−
→ −
→
minimize k fi − f˜i k, Mi hi = fi
(4.2)
−
→
fi ∈R#supp(fi )where Mi is similar to the Macaulay matrix (see [11, 2, 10, 15] for details). We note that we
can construct Mi of full column rank since Gcl is a (minimal) Gröbner basis hence the residualof monomial reduction by Gcl is unique and does not depend on the order of reducers used in
Gcl . This can be solved by the exact arithmetic (the generalized inverse by LSP decomposition,see [5, 6] for example).
Example 2 [Continued from Example 1]
We compute Fcl0 for F̃app and Gcl from the example 1:
F̃app = {f˜1 (~x) = 0.01084x3 y + 0.891x3 , f˜2 (~x) = 0.503xy 3 + 0.1129x + 0.02201},1122266401590457
246239085291621
Gcl = {g1 (~x) = xy 3 + 5000000000000000
x, g2 (~x) = x3 − 3125000000000000000000
x2 }.

According to the discussion above, we have supp(f1 (~x)) = {x3 y, x3 , x2 y, x2 } and supp(f2 (~x)) ={xy 3 , x, 1}. Hence the problem is equivalent to the following set of least squares.




271


 503 1 0
1
 25000
891
 0 1 − 1000  →  1000−1129 →
 c 0  h1 =  0  ,  c2  h2 =  10000 
 1



2201
0
1000000 c1
0246239085291621
where c1 = − 3125000000000000000000
and c2 = 1122266401590457. By computing the generalized inverses
5000000000000000(Moore-Penrose inverses) and multiply them, we have the following Fcl0 ∈ R[~x].
105859375000000000000000000000000000000000 3
x y + 8701171875000000000000000000000000000000000
x3
Fcl0 = { 9765625000000060633687125254201498612807641
9765625000000060633687125254201498612807641
8341349014253661375000000000000000
685621953108857221875000000000000000− 9765625000000060633687125254201498612807641
x2 y − 9765625000000060633687125254201498612807641
x2 ,
29646955038160690740895624266330521
13208519383697812976500000000000
xy 3 + 262594818761387929060191534688490000
x}26259481876138792906019153468849
3
3
−10 2
−8 2

≈ {0.01084x y + 0.891x − 8.54154 × 10

x y − 7.02077 × 10 x , 0.503xy 3 + 0.1129x}.

In this case, we can easily conﬁrm that a Gröbner basis of the resulting polynomial system Fcl0
is the given basis Gcl hence Fcl0 is also a solution of the problem 5 in the next section.
/
7

The above problems 2 and 3 can be combined into the following problem so that resulting
Fcl0 is much better than that is computed from Gcl separately.
Problem 4 [Nearby polynomial system directly] For the given F̃app , G̃app ⊂ F[~x], compute
Fcl0 , Gcl ⊂ R[~x] that are close to F̃app , G̃app , respectively, such that Fcl0 is generated by ideal(Gcl )and Gcl is a Gröbner basis of its self in the exact sense.
/
We combine the minimization problems (3.2) and (4.2). Since the generalized inverse canbe computed over any ﬁeld so we extend the Macaulay like matrix M over R to that over
the rational function ﬁeld R(~p), we can solve the minimization problem (4.2) over R(~p). Then
we solve the minimization problem (3.2). The resulting Fcl0 is not diﬀerent from the problem
2 since Gcl is a (minimal) Gröbner basis hence we construct M of full column rank as noted
before.
However, if we solve the following modiﬁed version of the minimization problem (3.2) the
resulting Fcl0 is diﬀerent.
∑
minimize mx) − f˜i (~x)ki=1 kfi (~p~subject to ht(gi ) = ht(g̃i ) and Spoly(gi , gj )

Gpar

= 0.

For example, we get the following result for the example 2.
x, x3 },
Gcl = {xy 3 + 1129
5030
271
891 3
503
1129
Fcl0 = { 25000
x3 y + 1000
x , 1000
xy 3 + 10000x}.

5

Nearby System of the Ideal

In general, the resulting Fcl0 of problems 3 and 4 does not generate the ideal generated by
the given Gcl and only satisﬁes ideal(Fcl0 ) ⊆ ideal(Gcl ). This condition is not enough forunderstanding the relation between the given erroneous polynomial system and its approximateGröbner basis hence in this section, we consider the following sub-problem.
Problem 5 [Nearby polynomial system of ideal] For the given F̃app ⊂ F[~x] and Gcl ⊂ R[~x],compute Fcl ⊂ R[~x] satisfying ideal(Fcl ) = ideal(Gcl ) in the exact sense and Fcl is close to F̃app ./In this paper, we only give a suﬃcient condition for a special case, that there is no solution
to this problem. The minimal generators of the ideal (see [14, 4] for related problems) is our
main tool.
Definition 1 (Minimal Generators)
Let G ⊂ R[~x] be a generating set of the ideal I ⊆ R[~x]. If I 6= ideal(G \ {g}) for any g ∈ G,
then G is called a minimal generating set of I and the polynomials in G are called minimal
generators of I.
/
Lemma 2 Let I ⊆ R[~x] be the ideal generated by a minimal Gröbner basis G = {g1 , . . . , gm }.
If all the elements in G is a monomial, the cardinality of any generating set of I is larger thanor equal to m.
/
8

Proof We assume that the lemma is not valid hence there exists a generating set F ={f1 , . . . , fn } with n < m. G and F are generating sets of I hence I = ideal(G) = ideal(F ).
This means that there exist hij , sjk ∈ R[~x] such thatgi (~x) =n∑hij (~x)fj (~x), fj (~x) =

j=1

m
∑

sjk (~x)gk (~x).

k=1Composing those two expressions, we obtain
( n
)
m
∑
∑
gi (~x) =hij (~x)sjk (~x) gk (~x).
∑n

k=1

j=1

∑n
Though we do not havex)sjk (~x) = δik in general,x)sjk (~x) must have a
j=1 hij (~j=1 hij (~constant term for k =∑ i since g1 (~x), . . . , gm (~x) are monomials and G is minimal. In contrast,by the same reason, nj=1 hij (~x)sjk (~x) must not have any constant term for k 6= i.
Therefore, we have the following equations in R[~x]/ideal(~x).
n∑hij (~x)sjk (~x) = δik (i = 1, . . . , n) (k = 1, . . . , m).

j=1

This is equivalent to the following matrix representation.
HS = Em , H = (hij ) ∈ Rm×n , S = (sjk ) ∈ Rn×m
where Em is the identity matrix of dimension m. The assumption n < m means that thissystem does not have any solution hence the lemma is valid.
We note that the lemma is valid only for monomial ideals. In general, there are several
generating sets of I with fewer elements than that of minimal generating sets of Gröbner basesof I. For example, the ideal generated by F = {−4x3 − 4x2 + xy − 5y − 4, 7x3 − 9x2 y + 6xy 2 }has the reduced Gröbner basis with 4 elements and its minimal generating set has at least 3
elements.
Example 3 [Unfaithful Gröbner basis]
We show an example of the lemma with the input F̃app below.
F̃app = { 0.6533x3 + 0.1359xy 2 + 0.08952xyz + 0.5586y 2 z + 0.1688yz 2 + 0.9009z 3 + 0.7794x2+0.4555xy + 0.1825xz + 0.4381y 2 + 0.3805yz,
0.5142z 3 + 0.981xy + 0.1469yz + 0.06382z 2 ,0.3685x3 + 0.2276xyz + 0.4191xz 2 + 0.27289y 3 + 0.427y 2 z + 0.2659yz 2 + 0.9568yz}.
For this input, the following G̃app is one of approximate Gröbner bases w.r.t. the gradedlexicographic order (x  y  z), computed by Mathematica.
G̃app = {1.0z 2 , 1.0yz, 1.0y 2 , 1.0xz, 1.0xy, 1.0x2 }.
Trivially, we have Gcl = {z 2 , yz, y 2 , xz, xy, x2 } and this is a minimal generating set of ideal(Gcl ).
Therefore, by the lemma 2, there is no polynomial system close to F̃app whose Gröbner basis is
Gcl since it has only 3 elements which is fewer than that of Gcl .
/9Note that the resulting approximate Gröbner basis depends on the algorithm and assumptions (precision, accuracy and so on) we used. Hence the above example does not mean that
Mathematica’s approximate Gröbner basis is odd, and by the suggestion from the lemma 2 we
can have a chance to change assumptions or algorithms. This is a merit of doing a backward
error analysis for approximate Gröbner basis.

6

Conclusion

Computing an approximate Gröbner basis basically comes from numerical computations and do
not come from theoretical computations though we can use comprehensive Gröbner system tosolve the problem partially. However, as shown in this paper, for some backward error analysisof the resulting approximate Gröbner basis, we have the following interesting problems.
• For the given set of polynomials F , compute a close enough G which is a Gröbner basisof ideal(G).
• For the given set of polynomials F and Gröbner basis G of ideal(G), compute a closeenough set of polynomials to F , which generates a sub-ideal of ideal(G).
• For the given set of polynomials F and Gröbner basis G of ideal(G), compute a closeenough set of polynomials to F , which generates ideal(G).
We give a proof of concept method for solving some of the above problems. However,basically they are not solved and still open since the optimizations for the former problems are
not well analyzed and the necessary and suﬃcient condition for the last problem is not given.
The author thinks that solving these problems is very important for approximate Gröbner
basis and if solved we can discuss approximate Gröbner basis is well deﬁned or not in the exact
context. Some further examples can be found in the appendix.

Acknowledgements
The author wishes to thank Prof. Kaltofen and Lichtblau for their comments at Hybrid2011
which led me to the problem in this paper though it is not solved yet. This work was supported
in part by Japanese Ministry of Education, Culture, Sports, Science and Technology underGrant-in-Aid for Young Scientists, MEXT KAKENHI (22700011).

References[1] T. Becker, V. Weispfenning, and H. Kredel. Gröbner bases: a computational approach tocommutative algebra. Graduate texts in mathematics. Springer-Verlag, 1993.
[2] J.-C. Faugère. A new eﬃcient algorithm for computing Gröbner bases (F4 ). J. Pure Appl.
Algebra, 139(1-3):61–88, 1999.

10

[3] J.-C. Faugère and Y. Liang. Pivoting in Extended Rings for Computing ApproximateGröbner Bases. Mathematics in Computer Science, 5:179–194, 2011.
[4] Hans and Schoutens. Computing the minimal number of equations deﬁning an aﬃne curve
ideal-theoretically. Journal of Pure and Applied Algebra, 177(1):95 – 101, 2003.
[5] O. H. Ibarra, S. Moran, and R. Hui. A generalization of the fast lup matrix decomposition
algorithm and applications. Journal of Algorithms, 3(1):45 – 56, 1982.
[6] C.-P. Jeannerod. Lsp matrix decomposition revisited. Technical Report Research Report
2006-28, École normale supérieure de Lyon, LIP, 2006.
[7] E. Kaltofen, J. P. May, Z. Yang, and L. Zhi. Approximate factorization of multivariate polynomials using singular value decomposition. Journal of Symbolic Computation,
43(5):359 – 376, 2008.
[8] E. Kaltofen, Z. Yang, and L. Zhi. Approximate greatest common divisors of several polynomials with l inearly constrained coeﬃcients and singular polynomials. In ISSAC 2006,
pages 169–176. ACM, 2006.
[9] D. Kapur, Y. Sun, and D. Wang. A new algorithm for computing comprehensive Gröbner
systems. In Proceedings of the 2010 International Symposium on Symbolic and Algebraic
Computation, ISSAC ’10, pages 29–36, New York, NY, USA, 2010. ACM.
[10] A. Kondratyev, H. J. Stetter, and S. Winkler. Numerical computation of Gröbner bases.
In Proceedings of CASC2004 (Computer Algebra in Scientific Computing), pages 295–306,
2004.
[11] D. Lazard. Gröbner bases, Gaussian elimination and resolution of systems of algebraic
equations. In Computer algebra (London, 1983), volume 162 of Lecture Notes in Comput.
Sci., pages 146–156. Springer, Berlin, 1983.
[12] D. Lichtblau. Gröbner bases in mathematica 3.0. The Mathematica Journal, 6(4):81 – 88,
1996.
[13] D. Lichtblau. Exact computation using approximate gröbner bases. Work presented at
ACA 2008, Applications of Computer Algebra. Session: Gröbner Bases and their Applications, 2008. http://library. wolfram.com/infocenter/Conferences/7537/.
[14] Y. Luo and Z. Lu. An estimation of the number of elements of minimal generators
for a polynomial ideal. MM Research Preprints Vol.25, pages 179–189, KLMM, AMSS,
Academia Sinica, 2006.
[15] K. Nagasaka. Computing a structured gröbner basis approximately. In Proceedings of the36th international symposium on Symbolic and algebraic computation, ISSAC ’11, pages
273–280, New York, NY, USA, 2011. ACM.

11

[16] K. Nagasaka. A symbolic-numeric approach to gröbner basis with inexact input.
Work presented at Hybrid 2011, Fields Institute Workshop on Hybrid Methodologies
for Symbolic-Numeric Computation, 2011. http://www.cs.uwaterloo.ca/conferences/ hybrid2011/slides/KosakuNagasaka.pdf.
[17] T. Sasaki and F. Kako. Computing ﬂoating-point Gröbner bases stably. In Proceedings of
SNC 2007, pages 180–189. ACM, New York, 2007.
[18] T. Sasaki and F. Kako. Term cancellations in computing ﬂoating-point Gröbner bases. In
Proceedings of CASC 2010, volume 6244 of Lecture Notes in Comput. Sci., pages 220–231,
Berlin, 2010. Springer.
[19] K. Shirayanagi. An algorithm to compute ﬂoating point Gröbner bases. In Proceedingsof the Maple summer workshop and symposium on Mathematical computation with Maple
V : ideas and applications, pages 95–106, Cambridge, MA, USA, 1993. Birkhauser Boston
Inc.
[20] K. Shirayanagi. Floating point Gröbner bases. In Selected papers presented at the international IMACS symposium on Symbolic computation, new trends and developments,
pages 509–528, Amsterdam, The Netherlands, The Netherlands, 1996. Elsevier Science
Publishers B. V.
[21] K. Shirayanagi and M. Sweedler. A theory of stabilizing algebraic algorithms. Technical
Report 95-28, pages 1–92, 1995. http://www.ss.u-tokai.ac.jp/s̃hirayan/msitr95-28.pdf.
[22] H. J. Stetter. Approximate Gröbner bases – an impossible concept? In Proceedings of
SNC 2005 (Symbolic-Numeric Computation), pages 235–236, 2005.
[23] A. Taylor. The inverse gröbner basis problem in codimension two. Journal of Symbolic
Computation, 33(2):221 – 238, 2002.
[24] C. Traverso and A. Zanoni. Numerical stability and stabilization of Groebner basis computation. In ISSAC 2002: Proceedings of the 2002 international symposium on Symbolicand algebraic computation, pages 262–269, New York, NY, USA, 2002. ACM.
[25] V. Weispfenning. Comprehensive Gröbner bases. J. Symbolic Comput., 14(1):1–29, 1992.
[26] V. Weispfenning. Gröbner bases for inexact input data. In Proceedings of CASC 2003
(Computer Algebra in Scientific Computing), pages 403–411, 2002.

Appendix
We show some further examples for approximate Gröbner basis [3, 15, 17] other than Mathematica’s. Note that all the examples in this paper can be found in the following URL with ourpreliminary implementation on Mathematica.
http://wwwmain.h.kobe-u.ac.jp/˜nagasaka/research/snap/issac12.nb

12Example 4
The following F̃app and G̃app are cited from the example 6.1 in [3] (w.r.t. the graded reverse
lexicographic order with x  y  z).
F̃app ={0.10519760 × 10−5 x − 0.70383719y − 0.74858720z + 1,
x − 0.10365584 × 10−5 y + 0.99083786z − 0.74199025,
0.12288986x + y − 0.11161051 × 10−5 z − 0.32687369,
0.49279128 × 10−1 x + y + 0.63703207z − 0.98207322},G̃app ={x + 0.24863582, y − 0.35742965, z − 0.99978662}.
Trivially, we have the following solution for the problem 2.
{}12431791
714859349989331
Gcl = x +
,y −
,z −
.
50000000
20000000
50000000
We have the following solution for the problem 3 (we show only them in ﬂoating-point representation with a limited number of decimal places since the full rational representations are toolarge here).
Fcl0 ≈ {1.05101 × 10−6 x − 0.703837y − 0.748587z + 1.0,
1.0x − 1.03566 × 10−6 y + 0.990838z − 0.74199,
0.12289x + 1.0y − 1.12662 × 10−6 z − 0.326874,
0.0492791x + 1.0y + 0.637032z − 0.982073}.
In this case, the resulting Fcl0 is close to F̃app and its diﬀerence is about 1.93532 × 10−8 in the
Euclidean norm. This result indicates that the given G̃app is enough close to Gröbner bases ofnearby systems of F̃app .
Moreover, if we minimize the diﬀerence between Fcl0 and F̃app as in the end of the section 4.
we get the following result (we show only them in ﬂoating-point representation).
Gcl ≈ {x + 0.248636, y − 0.35743, z − 0.999787},
Fcl0 ≈ {1.05172 × 10−6 x − 0.703837y − 0.748587z + 1.0,
1.0x − 1.03676 × 10−6 y + 0.990838z − 0.74199,
0.12289x + 1.0y − 1.11655 × 10−6 z − 0.326874,
0.0492791x + 1.0y + 0.637032z − 0.982073}.
The resulting Fcl0 and Gcl are close to the given system and Gröbner basis, respectively. The
diﬀerences in the Euclidean norm are 5.19825 × 10−9 and 2.49691 × 10−8 , respectively.
/
Example 5
The following F̃app and G̃app are cited from the example 3 in [15] (w.r.t. the graded lexicographic
order with x  y).
F̃app = {1.01x2 − 2.09y 2 + 0.002, 4.03x2 y + 3.06xy, 2.04x2 y + 0.504x2 + 1.504xy − 1.02y 2 },G̃app = {2.03847y 3 + 0.0485655x2 + 0.745414xy − 0.100253y 2 , 1.10491x2 − 2.28084y 2 }.
At ﬁrst, we construct a set of parametric polynomials:
Gpar = {g1 (~x) = y 3 + p12 x2 + p13 xy + p14 y 2 , g2 (~x) = x2 + p22 y 2 }.
13

In this case, the head terms of these two polynomials are co-prime hence there is no constraint
on parameters. Therefore, we have Gcl = G̃app with just rationalized coeﬃcients and we havethe following solution for the problem 3 (we show only them in ﬂoating-point representation).
Fcl0 ≈ {1.01199x2 − 2.08903y 2 ,4.03796x2 y + 0.00385432y 3 + 2.25236 × 10−16 x2 + 3.04946xy + 1.09111 × 10−16 y 2 ,2.0241x2 y − 0.00770481y 3 + 0.495998x2 + 1.52507xy − 1.02388y 2 }.
The resulting Fcl0 is far from the given system F̃app since F̃app is inconsistent. Moreover, if
we minimize the diﬀerence between Fcl0 and F̃app , the optimization is a little bit hard so we
could not ﬁnd the optimum. The result is the followings (we show only them in ﬂoating-point
representation).
Gcl ≈ {y 3 + 0.367287xy + 0.0029292y 2 , x2 − 2.05519y 2 },Fcl0 ≈ {1.00722x2 − 2.07003y 2 ,4.00659x2 y + 0.00383635y 3 + 0.00949385x2 + 3.02575xy + 0.00461946y 2 ,2.0084x2 y − 0.00766937y 3 + 0.49866x2 + 1.51321xy − 1.01277y 2 }.
The resulting Fcl0 is not closer than the above due to that we could not reach the optimum but
this is one of other consistent systems near the given.
/
Example 6
The following F̃app and G̃app are cited from the example 5 in [17] (w.r.t. the lexicographic orderwith x  y).
F̃app = {x3 + x2 y 2 , x2 y 2 − y 3 , −x2 y + 1.0001x2 + xy 2 + 0.9999y 2 },G̃app = {y 6 − 1.0001y 3 , xy 2 + 0.9999y 4 , x2 + 0.9998xy 3 + 0.9999xy 2 + 0.9998y 2 }.
In this case, we solve the optimization problem with 8 parameters and have the following
solution for the problem 2 (we show only them in ﬂoating-point representation). We note that
this is not the optimum solution since we could not reach the optimum in a reasonable period
hence we computed a solution within the diﬀerence 10−6 . Moreover, the resulting Gcl is very
close to G̃app but not the same.
Gcl ≈{1.00000y 6 − 1.00010y 3 , 1.00000xy 2 + 0.999900y 4 ,1.00000x2 + 0.999800xy 3 + 0.999900xy 2 + 0.999800y 2 }.
With this result, we have the following solution for the problem 3 (we show only them inﬂoating-point representation).
Fcl0 ≈ {1.00002x3 + 0.999980x2 y 2 + 0.0000199594xy 4 − 0.0000199614y 6 − 0.0000199594y 3 ,1.00003x2 y 2 − 0.0000250508xy 4 + 0.0000250533y 6 − 0.999975y 3 ,−1.00000x2 y + 1.00010x2 + 2.69562 × 10−8 xy 3
+1.00000xy 2 − 2.69589 × 10−8 y 5 − 9.54069 × 10−8 y 4 + 0.999900y 2 }.
The result indicates that F̃app lacks higher order terms in y to have its Gröbner basis with theshape of G̃app . In fact, Fδ = {x3 + x2 y 2 , x2 y 2 − y 3 , −x2 y + (1 + δ)x2 + xy 2 + (1 − δ)y 2 } has the14

following comprehensive Gröbner system and does not have any (minimal) Gröbner basis withy 6 if δ 6= 0.
δ = 0 ⇒ {x2 − y 5 − y 4 + y 2 , −xy 2 − y 4 , y 6 − y 3 },
δ = 1 ⇒ {2x2 + xy 2 − y 3 , xy 3 + y 3 , −y 4 + y 3 },
δ = −1 ⇒ {x3 + y 3 , x2 y + y 3 − 2y 2 , −xy 2 − y 3 , y 4 − y 3 },
δ 3 − δ 6= 0 ⇒ {−δy 4 + δy 3 , (−δ 2 + δ)xy 2 + (−δ 2 + δ)y 3 ,(−δ 4 − δ 3 + δ 2 + δ)x2 + (2δ 3 − 2δ)y 3 + (δ 4 − δ 3 − δ 2 + δ)y 2 }.
However, we note that the aim of the method proposed in [17] is numerical stability hence theresulting F̃app is intended to have a similar shape of a Gröbner basis of Fδ with δ = 0.
/15