Bernard Mourrain
email: bernard.mourrain@inria.fr

GALAAD Philippe Trébuchet
email: philippe.trebuchet@lip6.fr

Stable Normal Forms for Polynomial System Solving

Keywords: Multivariate polynomial, quotient algebra, normal form, border basis, root-finding, symbolic-numeric computation

. This general border basis algorithm weakens the monomial ordering requirement for Gröbner bases computations. It is up to date the most general setting for representing quotient algebras, embedding into a single formalism Gröbner bases, Macaulay bases and new representation that do not fit into the previous categories. With this formalism we show how the syzygies of the border basis are generated by commutation relations. We also show that our construction of normal form is stable under small perturbations of the ideal, if the number of solutions remains constant. This new feature for a symbolic algorithm has a huge impact on the practical efficiency as it is illustrated by the experiments on classical benchmark polynomial systems, at the end of the paper.

Introduction

Solving polynomial systems is the cornerstone of many applications in domains such as robotics, geometric modeling, signal processing, chromatology, structural molecular biology etc. In these problems, the system has, most of the time, finitely many solutions and the equations often appear with approximate coefficients.

From a computational point of view, it is an actual challenge to develop efficient and stable methods to solve such problems. First backward stability is expected. The computed solutions should be the exact solutions of a system in the neighborhood of the input system. Efficiency is also mandatory to tackle the encountered polynomial systems. One can expect for instance that the behavior of the method depends mainly on the number of solutions, and partially on other extrinsic parameters such as the number of variables.

To handle the backward stability issue, one may consider classical numerical methods such as Newton-like iterations. However these local methods do not provide any guarantee of global convergence nor a complete description of all the roots. Algebraic methods, on the contrary, handle all the roots simultaneously. They reduce the problem to computing the structure of the quotient algebra A of the polynomial ring modulo the ideal I generated by the input system [START_REF] Elkadi | Introduction à la résolution des systèmes d'équations algébriques[END_REF]. Such a structure is given by a basis B of A as a vector space, and the tables of multiplication in A. Equivalently, it can be described by an algorithm of projection of the ring of polynomials K[x] onto the vector space B generated by B, along the ideal I. We call such a projection, a normal form for the ideal I.

From the knowledge of the multiplication tables, we deduce either an exact encoding of the roots through a rational univariate representation [START_REF] Rouillier | Solving zero-dimensional polynomial systems through Rational Univariate Representation[END_REF], [START_REF] Giusti | A Gröbner free alternative for polynomial system solving[END_REF], or a numerical approximation by eigenvector computation, [START_REF] Auzinger | An elimination algorithm for the computation of all zeros of a system of multivariate polynomial equations[END_REF], [START_REF] Mourrain | Computing isolated polynomial roots by matrix methods[END_REF], [START_REF] Stetter | Numerical polynomial algebra[END_REF]. Since the eigencomputation can be considered as a numerically wellcontrolled process [START_REF] Golub | Matrix computations[END_REF], the challenge becomes now to compute efficiently and in a stable way the quotient algebra structure A.

In the family of algebraic methods, resultant-based techniques (see eg. [START_REF] Macaulay | Some formulae in elimination[END_REF], [START_REF] Emiris | Matrices in Elimination Theory[END_REF], [START_REF] Busé | Using projection operators in computer aided geometric design[END_REF]) exploit the properties of coefficients matrices of monomial multiples of the input equations in some specific degree. The table of multiplications are obtained by explicit Schur complements in these matrices [START_REF] Emiris | Matrices in Elimination Theory[END_REF]. Their construction is deeply linked to the geometry of the underlying variety that make these methods very tolerant against small perturbations. Unfortunately they heavily rely on genericity hypotheses that reduce their applicability. Moreover, the size of the constructed matrices usually grows exponentially with the number of variables.

To avoid such a pitfall, so-called H-bases have also been studied [START_REF] Macaulay | The Algebraic Theory of Modular Systems[END_REF], [START_REF] Möller | H-bases for polynomial interpolation and system solving. multivariate polynomial interpolation[END_REF]. They proceed degree by degree and stop when the terms of highest degree of the computed polynomials generate the terms of highest degree of all the ideal I. The stopping criterion requires the computation of generators of the syzygies of these highest degree terms. Though it also yields a basis of the quotient ring A, without any apriori knowledge on its dimension, practically speaking, it also suffers from the swelling of the size of the linear systems to be solved.

The approach can be refined further by using a grading for which the highest term of a polynomial is a monomial. This leads to Gröbner basis computation (see eg. [START_REF] Cox | Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra[END_REF]). This approach also yields a basis of the quotient algebra A and a normal form for I. As in the other methods, their computation can be seen as just a triangulation of a certain matrix. Unfortunately these methods suffer from unavoidable instability: the monomial ordering attached to the Gröbner basis make the pivot selection strategy in the triangulation depend only on the symbolic structure of the rows of the matrix, and not on the numerical values of the coefficients appearing in these rows. This can lead to artificial unwanted singularities in the representation of the quotient ring (compare for instance the degree reverse lexicographic Gröbner basis of

p 1 = ax 2 1 + bx 2 2 + ε 1 x 1 x 2 , p 2 = cx 2 1 + dx 2 2 + ε 2 x 1 x 2 with ε 1 = ε 2 = 0 and ε 1 = 0, ε 2 = 0).
To circumvent this artificial difficulty, a new approach based on a normal form criterion which involves commutation relations (for bases B connected to 1) was first proposed in [START_REF] Mourrain | A new criterion for normal form algorithms[END_REF]. Further investigations of this technique [START_REF] Mourrain | Solving projective complete intersection faster[END_REF], [START_REF] Mourrain | Algebraic methods for numerical solving[END_REF], including the Ph.D. dissertation [START_REF] Ph | Vers une résolution stable et rapide des équations algébriques[END_REF] lead to a first version [START_REF] Mourrain | Generalised normal forms and polynomial system solving[END_REF] of a normal form algorithm, which allows to construct efficiently and in a stable way zero-dimensional quotient algebra representations. Similar investigations were also pursued in [START_REF] Kehrein | An algebraist's view on border bases[END_REF], [START_REF] Kehrein | A characterisation of border bases[END_REF], but in the more restrictive case where the basis is stable by division. Other investigations related to the stabilization of the normal form process can also be found in [START_REF] Stetter | Numerical polynomial algebra[END_REF].

In this paper, we discuss border basis algorithms in the general sense, that is for bases B which are connected to 1. See [START_REF] Mourrain | Pythagore's Dilemma, Symbolic-Numeric Computation and the Border Basis Method[END_REF] for an introductory presentation of their properties. As in [START_REF] Faugère | Efficient computation of zero-dimensional Gröbner bases by change of ordering[END_REF] or [START_REF] Faugère | A new efficient algorithm for computing Gröbner Basis (F4)[END_REF], our approach is based on linear algebra tools. As for H-bases, we use a grading of the polynomial ring, but the construction is optimized in the spirit of [START_REF] Mourrain | Solving projective complete intersection faster[END_REF]. We describes an efficient criterion based on commutation polynomials to check the normal form property. This leads to an algorithm, as presented in [START_REF] Mourrain | Generalised normal forms and polynomial system solving[END_REF], which has been improved to treat optimally the case when a syzygy of the components of highest degree is found, which is not a syzygy of the corresponding polynomials. We prove that the syzygies of a (general) border basis are generated by the commutation relations, giving a short and concise answer to a conjecture in [START_REF] Kehrein | A characterisation of border bases[END_REF] for basis stable by division. Meanwhile, works related to this conjecture for this special case were also investigated in [START_REF] Huibregtse | An elementary construction of the multigraded Hilbert scheme of points[END_REF]. Regarding the numerical stability of border bases, we prove that our construction of normal form is stable against small perturbations of the input system, if the number of solutions remains constant.

The paper is structured as follows. In the next section, we recall the notations, used in section 3 to prove the stopping criterion for generalized normal forms. In section 4, we show how to recover the syzygies from the commutation relations. In section 5, we recall briefly the maind idea of the algorithm described in [START_REF] Mourrain | Generalised normal forms and polynomial system solving[END_REF]. In section 6, we analyze the stability of this algorithm from a symbolicnumeric perspective. Finally, we show the efficiency of our implementation and its numerical behavior on classical polynomial benchmarks.

Notations

We recall some of the definitions stated in [START_REF] Mourrain | A new criterion for normal form algorithms[END_REF], [START_REF] Mourrain | Solving projective complete intersection faster[END_REF], [START_REF] Mourrain | Algebraic methods for numerical solving[END_REF] and add a few more that we will need in the sequel.

Let K be an effective field. The ring of n-variate polynomials over K will be denoted by R, R = K[x] = K[x 1 , . . . , x n ]. We consider n-variate polynomials f 1 , . . . , f s ∈ R. Our goal is to solve the system of equations f 1 = 0, . . . , f s = 0 over the algebraic closure K of K. These polynomials generate an ideal of K[x] that we call I. The quotient of K[x] modulo I will be denoted by A. From now on, we suppose that I is zero dimensional so that A is a finite dimensional K-vector space. The roots, with coordinates in the algebraic closure of K, will be denoted by

ζ 1 , . . . , ζ d , with ζ i = (ζ i,1 , . . . , ζ i,n ) ∈ K n .
The support supp(p) of a polynomial p ∈ K[x] is the set of monomials appearing in p with non-zero coefficients. Given a set S of elements of K[x], we denote by S the K-vector space spanned by the elements of S. Finally, we denote the set of all the monomials in the variables x = (x 1 , . . . , x n ) by M. A term is an element of the form λ • m with λ ∈ K -{0} and m ∈ M. For a subset S of M, we will denote by S c the set-theoretical complement of the set S in M. For any monomial m ∈ M, m • M denotes the set of all monomial multiples of m.

For any subset S of R, we denote by S + or D(S) the set

S + = S ∪ x 1 S ∪ • • • ∪ x n S, ∂S = S + \S.
S + is called the prolongation of S. For any k ∈ N, S [k] is S k times +•••+ the result of applying k times the operator + on S. By convention, S [0] is S.

If B ⊂ M contains 1, for any monomial m ∈ M, there exists k such that m ∈ B [k] . We say that a monomial m is of

B-index k if m ∈ B [k] -B [k-1]
, and we denote it by δ B (m).

A set of monomials B is said to be connected to 1, if and only if, for every monomial m in B, there exists a finite sequence of variables (x ij ) j∈ [1,l]

such that 1 ∈ B, ∀l ′ ∈ [1, l], Π j∈[1,l ′ ] x ij ∈ B and Π j∈[1,l] x ij = m.
A set of monomials B is stable by division, if for any m ∈ B and any variable x i such that m = x i m ′ (m ′ ∈ M), we have m ′ in B. Remark that a set B stable by division, is connected to 1. Definition 2.1 Let Λ be a monoid with a well order relation ≺, such that:

∀α, β, γ ∈ Λ, α ≺ β ⇒ γ + α ≺ γ + β A (Λ, ≺)-grading of K[x] is the decomposition of K[x] as the direct sum: K[x] = λ∈Λ K[x] [λ]
, with the following property:

∀f ∈ K[x] [α] , g ∈ K[x] [β] ⇒ f g ∈ K[x] [α+β] .
We denote by degree of f or deg Λ (f ), or deg(f ) (when no confusion is possible) and by Λ(f ), the following element of Λ:

Λ(f ) = min{λ ∈ Λ | f ∈ λ ′ λ K[x] [λ ′ ] }.
For any set

V ⊂ K[x], let V λ = λ ′ λ K[x] [λ ′ ] ∩ V . For any λ ∈ Λ, let λ + = min{λ ′ ∈ Λ; K[x] + λ ⊂ K[x] λ ′ } and let λ -= max{λ ′ ∈ Λ; K[x] + λ ′ ⊂ K[x] λ }.
In order not to be confused with different notions of degree, for any monomial m of K[x], we define the size of m, denoted by |m|, to be the integer

d such that m = x i1 • • • x i d , which itself imposes a grading.
Another classical grading is the one associated with a monomial ordering, where Λ = N n and ≺ is a monomial order (see [7, p. 328]) such that for all α = (α 1 , . . . , α n ) ∈ N n , we have

K[x] [α] = K x α1 1 • • • x αn n . Definition 2.2
We say that Λ is a reducing grading if Λ is a grading and if we have the property: for all monomials m, m ′ ∈ M, such that m ′ divides strictly m, Λ(m

′ ) ≺ Λ(m), Λ(m ′ ) = Λ(m).
Both gradings induced by the classical degree and a monomial ordering are reducing grading. Hereafter, we will denote by Λ a reducing grading.

Definition 2.3 A rewriting family F for a monomial set B is a set of polynomials F = {f i } i∈I such that supp(f i ) ⊂ B + , f i has exactly one monomial γ(f i ) (also called the leading monomial of f i ) in ∂B, if γ(f i ) = γ(f j ) then i = j,
Remark that the elements of F can be seen as rewriting rules for the leading monomial using monomials of B. Definition 2.4 A reducing family F of degree λ ∈ Λ for a set B is a set of polynomials such that F is a rewriting family for B, ∀m ∈ ∂B of degree at most λ, ∃f ∈ F | γ(f ) = m.

For the set B = {1, x 0 , x 1 , x 0 x 1 }, the set of polynomials F = {x 2 0 -1, x 2 1 -x 1 , x 2 0 x 1 -x 1 , x 2 1 x 0 -x 1 } is a reducing family of degree 3.
Notice that a reducing family of degree λ for a set B (connected to 1) allows to rewrite the monomials of B + λ modulo F as elements of B λ . This leads in fact, to the definition of the linear projection π F , associated to a reducing family for a set B connected to 1. Definition 2.5 Given a reducing family F of degree λ ∈ Λ for a set B connected to 1, we define the linear projection π F :

B + λ → B λ such that ∀m ∈ B λ , π F (m) = m, ∀m ∈ ∂B λ , π F (m) = m -f ;
where f ∈ F is the unique member of F such as m = γ(f ). We extend this construction to B + λ by K-linearity.

There is a parallel with the differential algebra terminology, which we want to highlight here. To a polynomial f (x 1 , . . . , x n ) ∈ R of degree at most δ, we can associate the differential equation f (∂ 1 , . . . , ∂ n )Φ(t 1 , . . . , t n ) = 0, where ∂ i is the derivation with respect to the variable t i . It is a linear equation in Φ. The solution Φ(t 1 , . . . , t n ) lives in the ring K[[t 1 , . . . , t n ]] of formal power series in t 1 , . . . , t n , which we can truncate in degree λ Λ(f i ). This set J λ (t) of truncated series in degree λ is called the space of λ-jets in the literature. See eg. [START_REF] Saunders | The geometry of jet bundles[END_REF] for more details.

Given a set of polynomials F ⊂ K[x] of degree at most λ, we consider the so-called solution manifold R λ of the differential system F (∂)(Φ) = 0 in J λ (t) (In our case, it is just a linear space). Given λ ′ ≺ λ and Φ ∈ J λ (t), we can forget the coefficient of degree bigger than λ ′ and project it on J λ ′ (t). The set of solutions of F (∂)(Φ) = 0 projected on J λ ′ (t), is then defined by the equations

F λ ′ (Φ ′ ) = 0 where F λ ′ = F ∩ K[x] λ ′ .
We denote it by π λ ′ (F ). We denote by D(F ) the new system which extends F with the

∂ i f (∂) = 0, for i ∈ 1 . . . n, f ∈ F , obtained by formal multiplication by the ∂ i . It is called the prolongation of F .
The system F of degree at most λ is said formally integrable if for any r ≥ 0, π λ (D r+1 (F )) = F . A technical condition of involutivity is introduced to ensure the regularity of the differential system [START_REF] Pommaret | Partial differential equations and group theory: new perspectives for applications[END_REF]. A result of Cartan-Kuranishi [START_REF] Cartan | Les systèmes différentiels extérieurs et leurs applications géométriques[END_REF][START_REF] Kuranishi | Cartan's prolongation theorem of exterior differential systems[END_REF][START_REF] Pommaret | Partial differential equations and group theory: new perspectives for applications[END_REF] asserts that any system F can be transformed by prolongation and projection into a (involutive) formally integrable system. The connection of this construction with the notion of Mumford regularity of polynomial systems has been detailed in [START_REF] Malgrange | Cartan involutivness = Mumford regularity[END_REF]. This correspondence has been used explicitly for solving polynomial equations in [START_REF] Reid | Solving nonlinear polynomial system via symbolic-numeric elimination method[END_REF]. This involutive division is also used to construct a family of normal form projection related to so-called involutive bases (see eg. [START_REF] Blinkov | Construction of Janet bases (I. monomial bases, II. polynomial bases)[END_REF]). In Janet basis construction, however one difference is that the variables do not play a symmetric role. So-called multiplicative variables are used to perform reduction and non-multiplicative to extend the polynomial vector space.

In the following, instead of working in the vector space of all polynomials of a given degree, we will consider completion procedures based on prolongations and projections relative to a specific set of monomials B. Dealing locally with this set of monomials related to the number of solutions of the system will allow us to improve significantly the linear algebra stages in this type of methods.

In the sequel, we will make a heavy use of multiplication operators by one variable that we define as follows:

M i,λ : B λ -→ B λ b → π F (x i b).
The subscript λ is redundant as soon as we know that F is a reducing family of degree λ, and we will omit this subscript in the sequel. Definition 2.6 Let F = {f 1 , . . . , f s } be a polynomial set, we denote by F λ the vector space:

F λ = {x α f i | Λ(x α f i ) ≤ λ} .
Obviously, we have F λ ⊂ (F ) λ where (F ) is the ideal generated by F . Next we introduce a definition, which is weakening the notion of monomial ordering for Gröbner basis: In case more than one monomial satisfy these conditions, the greatest monomial for the lexicographic order is chosen.

The monomial returned by the choice function has the same name as the leading monomial of an element of a reducing family. This is intended, as we will define a reducing family on the behalf of choice functions, and in this framework the two will coincide. Hereafter if S = {p 1 , . . . , p s } is a polynomial set, then we denote by γ(S) the set: γ(S) = {γ(p 1 ) . . . γ(p s )}. Definition 2.9 Let γ be a choice function refining a grading Λ. For any polynomials p 1 , p 2 ∈ K[x], let the C-polynomial relative to γ and (p 1 , p 2 ) be

C(p 1 , p 2 ) = lcm(γ(p 1 ), γ(p 2 )) κ(p 1 ) γ(p 1 ) p 1 - lcm(γ(p 1 ), γ(p 2 )) κ(p 2 ) γ(p 2 ) p 2 .
Let the C-degree of (p 1 , p 2 ) be Λ(lcm(γ(p 1 ), γ(p 2 ))) and let the leading monomial of the pair (p 1 , p 2 ) be lcm(γ(p 1 ), γ(p 2 )).

This is almost the same definition as a S-polynomial [START_REF] Cox | Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra[END_REF] when γ is a monomial ordering. We however use a new name to underline that now γ may not be a monomial ordering (i.e. a total order compatible with monomial multiplication). As we will see in the next section, the C-polynomials express commutation conditions for the M i,λ .

Generalized normal form criterion

Let F = {f 1 , . . . , f s } be a polynomial system and let I be the ideal generated by F . Remember that F λ (the K-vector space spanned by the monomial multiples of the f i , x α f i of degree λ ∈ Λ) is included in I λ . Thus, when I λ = F λ we can define a normal form modulo I, up to the degree λ as the projection of K[x] λ along F λ onto a supplementary space B λ . Hereafter, we consider a set B of monomials, containing 1.

Let F be a rewriting family, and let H = {m, ∃p ∈ F, γ(p) = m} be the set of their leading monomials then, obviously F allows us to define the projection π F of B ∪ H on B along F . However we may extend this projection using the following extension process: Definition 3.1 Let F be a rewriting family. For all m ∈ B, we define π e F (m) = m. For m ∈ B, there exists m ′ ∈ ∂B and r integers i 1 , . . . , i r ∈ [1, n], such that m = x i1 • • • x ir m ′ . We define π e F (m) by induction on k, as follows.

• if r = 0, π e F (m ′ ) is defined as π e F (m ′ ) = π F (m ′ ) = m ′ -f where f ∈ F is such that γ(f ) = m ′ . • ∀k, 1 ≤ k ≤ r, π e F (x i r-k • • • x ir m ′ ) = π F (x i r-k π e F (x i r-k+1 • • • x ir m ′ ))
, if this latter quantity is defined. Otherwise we say that π e F (m) is undefined. Remark that the above process allows us to define π e F only on monomials, and we extend it implicitly, by linearity. Remark also that this extension process is not defined in a unique way. Indeed, two different decompositions of a monomial m may lead to two different values of π e F (m). However the following theorem shows that this extension process becomes canonical as soon as we check some commutativity conditions. Theorem 3.2 Assume that B is connected to 1. Let F be a rewriting family, and let E be the set of monomials m such that for all decomposition of m as a product of variables, m

= x i0 • • • x i k , π F (x i0 π F (x i1 • • • π F (x i k ) • • •)) is defined.
Suppose that for all m ∈ E and all indexes i, j ∈ [1, n] such that x i x j m ∈ E, we have:

π e F (x i π e F (x j m)) = π e F (x j π e F (x i m)).
Then π e F coincides with the linear projection π S of E on B along the vector space spanned by the polynomials S = {x α f, α ∈ N n , f ∈ F and x α γ(f ) ∈ E}.

Proof. Remark that the way we define it, makes π e F inherently a linear multivalued map. Hence to prove the theorem we have first to show that under the above hypotheses, π e F becomes a well defined map, and next that this well defined linear map coincide with the projection π S of E on B along S .

Remark also that E is obviously stable by monomial division: if all the possible decompositions of m as a product of variables m

= x i0 • • • x i k are such that π F (x i0 • • • π F (x i k )) is defined, then a fortiori if m ′ is a divisor of m,
this property is true for m ′ . Let us show that the extension process is independent of the way m is decomposed as a product of variables. Let m = x i0 m ′ = x i1 m ′′ with i 0 = i 1 and m, m ′ , m ′′ ∈ E, then there exists m ′′′ ∈ E (since E is stable by monomial division) such that m = x i0 x i1 m ′′′ . As m, m ′ , m ′′ , and m ′′′ are in E, π e F (m ′ ), π e F (m ′′ ), π e F (x i0 m ′ ), π e F (x i1 m ′′ ), and π e F (m ′′′ ) are defined and we have:

π e F (x i0 π e F (m ′ )) = π e F (x i0 π e F (x i1 π e F (m ′′′ ))), π e F (x i1 π e F (m ′′ )) = π e F (x i1 π e F (x i0 π e F (m ′′′ ))).
The commutation condition guarantees that the two quantities are equal, so that the definition of π e F does not depend on the way to write m as a product of variables.

Next we have to show that π e F and π S coincide on their common set of definition. We do it by induction on the size of the monomials: It is true that π e F (1) = π S (1) = 1 (since 1 ∈ B). For any monomial m = 1 in E, the property of connectivity of B and the definition of E gives us: ∃m ′ ∈ E and i 0 ∈ [1, n] such that m = x i0 m ′ and π e F (m ′ ) is defined, so that we have:

π e F (m) = π e F (x i0 m ′ ) = def π e F (x i0 π e F (m ′ )) = induction π e F (x i0 π S (m ′ )) ∈ B .
Now by induction, m ′ -π S (m ′ ) ∈ S λ -where λ = Λ(m) and

m -π e F (m) = x i0 (m ′ -π S (m ′ )) + (x i0 π S (m ′ ) -π e F (x i0 π S (m ′ ))) ∈ S .
Thus π e F (m) is the projection of m on B along S .

2 Suppose now that we are given a reducing family of degree δ instead of a rewriting family. Then we can further extend the above theorem with the help of the following lemma. Lemma 3.3 Let F be a reducing family of degree λ for a set B connected to 1, and suppose that ∀f ∈ F, Λ(γ(f )) = Λ(f ). With the notation of Theorem 3.2, the set E contains the set of monomials of degree less than or equal to λ.

Proof. Let m ∈ M λ be a monomial of degree less or equal to λ, then m can be written as m = x i1 . . .

x i d with d = |m|. Let us prove by induction on k ≤ d, that p k = π F (x i k π F (• • • π F (x i1 )) • • •) is defined and that Λ(p k ) ≤ Λ(x i k • • • x i1 ). Consider now x i k+1 p k ∈ B + . For m ′ ∈ supp(x i k+1 p k ) ∩ B, we have π(m ′ ) = m ′ and by induction hypothesis Λ(m ′ ) ≤ Λ(x i k+1 • • • x i1 ). For m ′ ∈ supp(x i k+1 p k ) ∩ ∂B,
as F is a reducing family of degree λ, we have a rewriting rule for m ′ . The hypothesis that ∀f ∈ F, Λ(γ(f )) = Λ(f ) implies that m ′ rewrites in terms of monomials of degree bounded by Λ(

x i k+1 • • • x i1 ). This proves p k+1 := π F (x i k+1 p k ) is defined and Λ(p k+1 ) ≤ Λ(x i k+1 • • • x i1 ). This proves by induction that π e F (x i1 • • • π e F (x i d )) is defined, for any decomposition m = x i1 • • • x i d ∈ M λ so that m ∈ E. This ends the proof. 2
Theorem 3.4 Let F be a reducing family of degree λ for a set B connected to 1. If we have:

• ∀f ∈ F, Λ(γ(f )) = Λ(f ). • M j,λ • M i,λ -= M i,λ • M j,λ -, for 1 ≤ i, j ≤ n,
then, we can extend π F to a linear projection π e F from K[x] λ onto B λ with kernel F λ . Proof. As F is a reducing family of degree λ, by Lemma 3.3, we have E ⊃ M λ .

Let us prove that for all m ∈ M λ --and all pairs of indices (i, j), there exists a way to define π e F such that π e F (x i π e F (x j m)) = π e F (x j π e F (x i m)).

As M λ --⊂ M λ ⊂ E, π e F (m) is defined and supp(π e F (m)) ⊂ B. We define π e F (x i m) = π F (x i π e
F (m)) and, similarly, π e F (x j m) = π F (x j π e F (m)). With this definition we have:

π e F (x i π e F (x j m)) = M i,λ (M j,λ -(π e F (m))) = M j,λ (M i,λ -(π e F (m))) = π e F (x j π e F (x i m))
. which proves the commutation property. We end the proof by applying Theorem 3.2. 2

Corrolary 3.5 With the hypothesis of Theorem 3.4, we have

K[x] λ = B λ ⊕ F λ .
Let us give here another effective way to check that we have a projection from F λ (vector space spanned by the monomial multiples of the f i of degree λ) onto B λ (element of degree λ of the vector space spanned by B) starting from a reducing family of degree λ, without computing explicitly the multiplication operators.

Theorem 3.6 Let λ ∈ Λ. Let F be a reducing family of degree λ ∈ Λ, for B. Assume that ∀ f ∈ F, Λ(γ(f )) = Λ(f ) and let π F be the induced projection from

B + λ onto B λ . Then ∀f, f ′ ∈ F λ such that C(f, f ′ ) ∈ B + λ , π F (C(f, f ′ )) = 0
iff π F extends uniquely as a projection π e F from K[x] λ onto B λ such that ker(π e F ) = F λ . Proof. By Theorem 3.4, we have to show that this condition is equivalent to the commutation of the operators M i,λ ′ , λ ′ < λ on the monomials of B λ --. For any m ∈ B λ --and any

i 1 = i 2 such that x i1 m ∈ ∂B, x i2 m ∈ ∂B, there exists f, f ′ ∈ F λ -such that γ(f ) = x i1 m, γ(f ′ ) = x i2 m. Thus, we have π F (x i1 m) = γ(f ) -f , π F (x i2 m) = γ(f ′ ) -f ′ and C(f, f ′ ) = x i2 f -x i1 f ′ ∈ B + λ . Consequently, M i2,λ (M i1,λ -(m)) -M i1,λ (M i2,λ -(m)) = M i2,λ (γ(f ) -f ) -M i1,λ (γ(f ′ ) -f ′ ) = π F (x i2 γ(f ) -x i2 f ) -π F (x i1 γ(f ′ ) -x i1 f ′ ) = π F (x i1 f ′ -x i2 f ) = π F (C(f ′ , f )).
which is zero by hypothesis. A similar proof applies if

x i1 m ∈ B or x i2 m ∈ B. Conversely, since ker(π e F ) = F λ and C(f, f ′ ) ∈ F λ ∩ B + λ , we have that π F (C(f ′ , f )) = π e
F (C(f ′ , f )) = 0, which proves the equivalence and Theorem 3.6. 2

Remark 3.7 In this proof, we have shown that if the C-polynomials up to the degree λ reduce to 0, then the multiplication operators M i,λ commute.

Definition 3.8 A reducing family F for all degrees λ ∈ Λ on a set B of monomials, connected to 1 will be called a border basis for B.

Finally, the previous results leads to a new proof of Theorem 3.1 of [START_REF] Mourrain | A new criterion for normal form algorithms[END_REF]:

Theorem 3.9 Let F be a border basis for a set B of monomials, connected to 1, let π F be the corresponding reduction from B + onto B , and let

M i : B → B such that ∀ b ∈ B , M i (b) = π F (x i b). Then, M j • M i = M i • M j ,

Syzygies and Commutation Relations

In this section, we analyze more precisely the relations between the polynomials of the border basis F = (f ω ) ω∈∂B where f ω = ω -ρ ω with ρ ω ∈ B . These relations or syzygies form a module that we denote by

Syz(F ) = { ω h ω e ω ∈ K[x] ∂B ; ω h ω f ω = 0},
where (e ω ) ω∈∂B is the canonical basis of K[x] ∂B . If F is a border basis family constructed from an initial set of polynomials H = {h 1 , . . . , h s }, we can express f ω ∈ F in terms of the polynomials in H (and conversely) so that a syzygy on F induces a syzygy on H (and conversely). Therefore, we are going here to consider only the syzygies on F . For any b ∈ B and i ∈ [1, n], x i b ∈ B + can be projected in B along F :

π F (x i b) = x i b - ω∈∂B µ i b,ω f ω .
More generally, for any p ∈ K[x], we denote by µ i p,ω the coefficient

µ i b,ω in π F (x i b) for b = π F (p) ∈ B and by µ i (p) = ω∈∂B µ i p f ω . Notice that if x i p ∈ B then µ i (p) = 0. For any m = x i3 • • • x i k ∈ B and i 1 , i 2 ∈ 1 . . . n, the two decompositions π F (x i1 π F (x i2 m)) = π F (x i2 π F (x i1 m)) yield the syzygy x i1 ω∈∂B µ i2 m,ω f ω -x i2 ω∈∂B µ i1 m,ω f ω - ω∈∂B (µ i2 xi 1 m,ω -µ i1 xi 2 m,ω ) f ω = 0. (1)
These relations can also be rewritten as:

x i1 µ i2 (m) + µ i1 (x i2 m) -x i2 µ i1 (m) -µ i2 (x i1 m) = 0.
We denote by Ξ the module of K[x] ∂B generated by these syzygies. It is also the module generated by the relations of commutation

M i1 • M i2 (b) -M i2 • M i1 (b) = 0 for all b ∈ B, i i , i 2 ∈ [1 . . . n].
We distinguish the following relations:

• If x i1 m, x i2 m ∈ B, then µ i1 (m) = µ i2 (m) = 0, µ i1 (x i2 m) = µ i2 (x i-1 m)
= 0 and m does not yield a non-trivial relation of the form (1).

• If x i1 m ∈ B but x i2 m ∈ ∂B, and x i1 x i2 m ∈ ∂B, then π F (x i2 m) = x i2 m -f xi 2 m
and we have the relation

x i1 f xi 2 m -f xi 1 xi 2 m + ω∈∂B µ i1 xi 2 m,ω f ω = 0. ( 2
)
• If x i1 m ∈ B, x i2 m ∈ ∂B, and x i1 x i2 m ∈ B, then π F (x i2 m) = x i2 m -f xi 2 m
and we have the relation

x i1 f xi 2 m + ω∈∂B µ i1 xi 2 m,ω f ω = 0. ( 3
) • If x i1 m ∈ ∂B and x i2 m ∈ ∂B, then π F (x i1 m) = x i1 m -f xi 1 m , π F (x i2 m) = x i2 m -f xi 2 m
and we have the syzygy

x i1 f xi 2 m -x i2 f xi 1 m - ω∈∂B (µ i2 xi 1 m,ω -µ i1 xi 2 m,ω )f ω = 0 (4)
The syzygies (2) and ( 4) are called respectively next-door and across-the-street relations in [START_REF] Kehrein | A characterisation of border bases[END_REF]. The syzygies (3) does not exist if B is stable under division (since in this case, x i2 m ∈ B implies x i1 x i2 m ∈ B). All these syzygies are simply the non-trivial relations induced by the "border" C-polynomials (see Definition 2.9).

Let us now prove that the module of syzygies is generated by these commutations syzygies. For any monomial m = x i1 • • • x i k , we can rewrite by induction its projection as:

π F (m) = π F (x i1 π F (x i2 • • •) = m - l=1...k x i1 • • • x i l-1 ω∈∂B µ i l xi l+1 •••x k ,ω f ω (5)
with the convention that x i k+1 = 1. We denote by

Ξ xi 1 ,...,xi k = l=1...k x i1 • • • x i l-1 ω∈∂B µ i l xi l+1 •••x k ,ω e ω the corresponding element of K[x] ∂B .
Notice that this decomposition depends on the order of the

decomposition m = x i1 • • • x i k as a product of variables. Lemma 4.1 If m = x i1 • • • x i k = x j1 • • • x j k then Ξ xi 1 •••xi k -Ξ xj 1 ,...,xj k ∈ Ξ.

Proof. Consider first a permutation of two variables

m = m 1 x i l x i l+1 m 2 = m 1 x i l+1 x i l m 2 (with m 1 = x i1 • • • x i l-1 , m 2 = x i l+2 • • • x i k ). Using (5), the two way of projecting m = m 1 x i l x i l+1 m 2 = m 1 x i l+1 x i l m 2 yield the syzygy Ξ ...,xi l ,xi l+1 ,... -Ξ ...,xi l+1 ,xi l ,... = m 1 × x i l ω∈∂B µ i l+1 m2,ω e ω -x i l+1 ω∈∂B µ i l m2,ω e ω + ω∈∂B (µ i l xi l+1 m2,ω -µ i l+1 xi l m2,ω )e ω
which is in Ξ. By iterated permutations of two variables, we transform the sequence x i1 , . . . , x i k into the sequence x j1 , . . . , x j k . This allows us to rewrite

Ξ xi 1 •••xi k into Ξ xj 1 ,...,xj k modulo Ξ. 2 Lemma 4.2 If m θ = m ′ θ ′ with θ, θ ′ ∈ ∂B and m, m ′ ∈ M, then m e θ ≡ m ′ e θ ′ + ω∈∂B p ω e ω mod Ξ with p ω ∈ K[x] of degree < max(|m|, |m ′ |).
Proof.

If m = x i1 • • • x i d with θ = x i d+1 b ∈ ∂B and b ∈ B, the projection formula (5) of m θ has the form π F (m θ) = m θ -x i1 • • • x i d f θ - l=1...d x i1 • • • x i l-1 ω∈∂B µ i l xi l+1 •••xi d θ,ω f ω since x i d+1 b = θ and π F (θ) = θ -f θ . If m ′ = x j1 • • • x j d ′ and θ ′ ∈ ∂B with mθ = m ′ θ ′ , by Lemma 4.1,
the two decompositions yield the syzygy

x i1 • • • x i d e θ -x j1 • • • x j d ′ e θ ′ + l=1...d x i1 • • • x i l-1 ω∈∂B µ i l xi l+1 •••xi d θ,ω e ω - l=1...d ′ x j1 • • • x j l-1 ω∈∂B µ j l xj l+1 •••xj d ′ θ ′ ,ω e ω
as an element of Ξ. This syzygy is of the form m e θ -m ′ e θ ′ + ω∈∂B p ω e ω with deg(p ω ) < max(d, d ′ ), which proves the lemma. 2 This yields the following result for a border basis, conjectured in [START_REF] Kehrein | A characterisation of border bases[END_REF] for the case where B is stable by division:

′ ∈ M, θ ′ ∈ ∂B such that m θ = m ′ θ ′ and δ B (m ′ θ ′ ) = |m ′ | + 1. This implies that |m| > |m ′ |. Applying lemma 4.2, the product m e θ can be reduced modulo Ξ, to m ′ e θ ′ + ω∈∂B q ω e ω ,
with deg(q ω ) < |m|. Iterating this reduction, we may assume that each term λ m e ω (λ

∈ K -{0}, m ∈ supp(p ω ), ω ∈ ∂B) is such that δ B (m ω) = |m| + 1.
Notice that the polynomial m f ω has only one monomial of maximal B-index, which is m ω.

As ω p ω f ω = 0, there exist θ = θ ′ ∈ ∂B and monomials m ∈ supp(p θ ), m ′ ∈ supp(p θ ′ ) such that m θ = m ′ θ ′ and δ B (m θ) is maximal among all terms of the syzygy. By lemma 4.2, we can replace this pair (m e θ , m ′ e θ ′ ) modulo Ξ by a sum of terms of smaller degree. This transformation reduces either the number of terms with maximal B-index or the degree of the polynomials p ω .

Since we cannot iterate it infinitely, we deduce that σ is in Ξ. 2

Algorithmic issues

From the preceding sections, we deduce an algorithm as it is done in [START_REF] Mourrain | Generalised normal forms and polynomial system solving[END_REF]. The main idea is to translate the previous concepts into linear algebra. From Section 3 to compute effectively a normal form, one has to find a (monomial) basis B of the quotient algebra connected to 1, and border relations such that the multiplication operators commute. The algorithm described in [START_REF] Mourrain | Generalised normal forms and polynomial system solving[END_REF], is a fix point method, which updates

• a potential monomial basis B of the quotient algebra,

• a set P of polynomials or rewriting rules (with one monomial of their support in ∂B and the remaining monomials in B), until a fix point is reached. At each step of the algorithm, the following operations are performed:

1. The set P ′ of polynomials of P + with support in B + is computed.

2. By taking linear combinations, a basis P of the vector space P ′ is computed, such that each element of this basis has at most one monomial in ∂B (and the other in B).

3. The C-polynomials of the elements of P with their support in B + are computed and reduced by P .

4. If non-zero polynomials with support in B appear, the potential basis B and the polynomial set P are updated. The update of B is done by removing some parts of B. The update of P is done by combining the elements of P and the reduced C-polynomials, in order to get rewriting rules for the new set B.

The details and the technical proof of termination of the algorithm are available in [START_REF] Mourrain | Generalised normal forms and polynomial system solving[END_REF]. We mention here that we have improved the algorithm described in this paper since then: the ways the degree drops are treated in [START_REF] Mourrain | Generalised normal forms and polynomial system solving[END_REF] is now done to avoid to the repeated execution of similar reductions.

Stability of the bases

This section is devoted to the study of the stability under numerical perturbations, of the bases computed by the previous algorithm. In many real-life problems, the system f = (f 1 , . . . , f s ) to be solved is given only with limited accuracy. However, most of the time, one also knows that the structure of the solutions is invariant in a small neighborhood of the system. Hence one of the feature that is often required to polynomial solvers is to produce a representation of the quotient algebra that is stable in a small neighborhood of the initial system. The structural numerical stability of the basis is expected in order to have a smooth behavior of the coefficients of the representation in the neighborhood of f = (f 1 , . . . , f s ). By definition, a neighborhood of f is an open set in the space of vector of polynomials (h 1 , . . . , h s ) such that Λ(h i ) Λ(f i ) (i = 1, . . . , n) and which contains f . For ǫ > 0, we define by N ǫ (f ) the set of systems (h 1 , . . . , h s ) such that Λ(h i ) Λ(f i ) and the coefficient vector of h i is at most at distance ǫ from the coefficient vector of f i (for the ∞-norm). Assumption 6.1 Hereafter, γ denotes a choice function refining a reducing grading Λ, such that for all p ∈ R, γ(p) depends only on the support of p and not on the numerical value of its monomial coefficients (e.g. Macaulay's choice function, grevlex choice function,. . . ). Let γ ǫ be the choice function that for any p ∈ R, applies the choice function γ on the monomials of p, which coefficient norm is bigger than ǫ. Theorem 6.2 Let f = (f 1 , . . . , f s ) be a zero dimensional polynomial system such that in a neighborhood U of f , all systems have the same number D of complex solutions, counted with multiplicities. Then for all ǫ > 0 small enough, there exists ν > 0 such that for any system f ′ ∈ N ν (f ) ⊂ U , the basis B computed with γ satisfying Assumption 6.1 for the system f is also a basis for the system f ′ .

Proof. Let us consider the matrix M whose rows correspond to the coefficient vectors of the monomial multiples m f i , with deg(m) + deg(f i ) ≤ κ + d 0 where κ is the number of loops in Algorithm [START_REF] Mourrain | Generalised normal forms and polynomial system solving[END_REF] and d 0 the maximum degree of the polynomials f i . The columns are indexed by all the monomials of degree ≤ κ + d 0 .

We denote by B the monomial set obtained as a basis of A = R/I by applying Algorithm [START_REF] Mourrain | Generalised normal forms and polynomial system solving[END_REF] to f 1 , . . . , f s with the choice function γ. By construction, the set of monomials indexing the columns of M contains ∂B.

Let M g be the same matrix as M but constructed with the polynomials f i replaced by generic equations, i.e. equations with indeterminate coefficients having the same support as f 1 , . . . , f s . Let N be the block of columns of M indexed by monomials not in B and let N g be the corresponding block in M g .

Since the operations of Algorithm [START_REF] Mourrain | Generalised normal forms and polynomial system solving[END_REF] consist in computing linear combinations of some monomial multiples of the polynomials P (see Section 5 and [29]) and thus of monomial multiples of f i of degree ≤ κ + d 0 , the complete computation can be reinterpreted as an optimized triangulation procedure of the block N .

The block N g specialized at f is invertible, because any monomial not in B can be reduced by the computed border basis of f to an element in B . This implies that N g specialized at f ′ is also invertible, for f ′ ∈ N ν (f ) with ν > 0 sufficiently small. Therefore any monomial of ∂B can be reduced modulo the ideal (f ′ ) to an element in B . Consequently, B (which contains 1) is a generating set of the quotient algebra

A ′ = R/(f ′ ) for any f ′ ∈ N ν (f ).
As the number of solutions D = |B| (counted with multiplicity) is left unchanged by small perturbations in the neighborhood N ν (f ) of f , the monomial set B, that has exactly cardinality D, is also a basis of the quotient algebra A ′ = R/(f ′ ) for the perturbed system f ′ .

2 Consider now a slight modification of Algorithm [START_REF] Mourrain | Generalised normal forms and polynomial system solving[END_REF]: the coefficients whose norm is less than ǫ are simply ignored in all the steps of Algorithm [START_REF] Mourrain | Generalised normal forms and polynomial system solving[END_REF]. This means that they will not be taken into account for choosing a leading monomial, or deciding if a polynomial is nonzero. This small variant will be denoted as the ǫ-algorithm in the next theorem. Remark here that this behavior is quite classical in fact, it is more or less what is usually done when neglecting small coefficients in a numerical algorithm. Remark also that the following theorem performs rigorously, and that the computed result is not an approximation of the true quotient algebra! Then the following holds: Theorem 6.3 Let f = (f 1 , . . . , f s ) be a zero dimensional polynomial system such that in a neighborhood U of f , all systems have the same number D of complex solutions, counted with multiplicities.

Then for all ǫ > 0 small enough, there exists ν > 0 such that for any system f ′ ∈ N ν (f ) ⊂ U , the basis B computed with γ satisfying Assumption 6.1 for the system f is also the basis obtained with γ ǫ and the ǫ-algorithm for the system f ′ .

Proof. By Theorem 6.2, B is also a basis of the quotient algebra R/(f ′ ). This basis B is obtained by applying Algorithm [START_REF] Mourrain | Generalised normal forms and polynomial system solving[END_REF] to f . The result of this algorithm does not change for the system f if we replace the choice function γ by γ ǫ for ǫ > 0 small enough (eg. smaller than the minimum of the norm of the coefficients of the polynomials on which γ is applied).

Let us show by induction on the loop index k of the algorithm that the steps and the polynomials computed by the ǫ-algorithm with γ ǫ are the same as for the direct algorithm, up to the terms of norm smaller that ǫ.

It is true obviously for the first step k = 1. Let us suppose now that steps 1, . . . , k ′ of Algorithm [START_REF] Mourrain | Generalised normal forms and polynomial system solving[END_REF] ran on f and its ǫ variant ran on f ′ are structurally the same and let us show that step k ′ +1 is also structurally the same for the two computations. The coefficients of all these constructed polynomials are rational functions of the coefficients of f ′ , which are well defined in a neighborhood of f . If f ′ is close enough to f , the monomials which are in the support of the constructed polynomials for f ′ but not in the support of the constructed polynomials for f , have coefficients of norm smaller then ǫ.

If, by hypothesis, the first k ′ steps are structurally identical, the same polynomials, up to terms of norm smaller than ǫ, appear when selecting the polynomials in P + , and the same C-polynomials are constructed (see Section 5 and [29]). By continuity of the coefficients of the constructed polynomials, the same pivots (of norm bigger than ǫ) are used to construct the new elements in P . Similarly, in a neighborhood of f , up to terms of small norm, the C-polynomials not reducing to zero are the same for the two computations. If choices of leading monomials are to be performed, then, by Definition 6.1, γ ǫ will select the same monomials for f ′ and f . Finally at the end of step k ′ + 1 the same computations are performed, up to terms of small norm and the coefficients of the new constructed polynomials are rational functions of the coefficients of f ′ , which are well defined in a neighborhood of f . This ends the induction showing that the two computations are structurally identical for f ′ ∈ N ν (f ) with ν > 0 small enough. Hence B will also be found as a basis of R/(f ′ ) with this ǫ-algorithm. 2

The rewriting rules obtained from the ǫ-algorithm are close to the exact rewriting rules of the system f ′ . Their numerical quality can be improved by iterative refinements such as Newton-like iterations using the commutation relations. Such approach has been investigated in [START_REF] Stetter | Numerical polynomial algebra[END_REF]. Remark 6.4 (Numerical certification) Theorem 6.3 shows the continuity of the normal form computation with respect to the coefficient of the input system. It states that there exists a region of stability for the computed quotient algebra representation, but it is an open problem to compute apriori the value ǫ and ν for a given polynomial system in order to control the size of the allowed perturbations. This problem is the subject of further work. Remark 6.5 (Flatness) Theorem 6.3 also shows that if we consider a rationally parametrized family of systems f t ∈ N ν (f ) for all t ∈ [0, 1], such that f 0 = f and F 0 is the border basis for B, then the set B is also a basis of A t = R/(f t ). Moreover, the border basis F t of f t for B is of the form F t = (ω -ρ ω,t ) ω∈∂B , where ρ ω,t ∈ B is a continuous (rational) function of t on [0, 1] such that F 0 = (ω -ρ 0,ω ) ω∈∂B . This also implies that the C-relations (2) and ( 4) generating the syzygies of F t are continuous (rational) functions of t ∈ [0, 1], which coincide with the C-polynomials relations of F 0 at t = 0. Consequently any syzygy of F 0 which is a combination of the C-relations can be deformed continuously into a syzygy of F t (for t ∈ [0, 1]). In other words, the systems f ′ in the neighborhood N ν (f ) are flat deformations of the system f [START_REF] Eisenbud | Commutative Algebra with a view toward Algebraic Geometry[END_REF].

Experimentation

The algorithm described in the previous section is implemented in the library Synaps2 . It corresponds to about 50 000 lines of C++-code. It involves a direct sparse matrix solver. The numerical approximation of the roots are obtained by eigenvalues computation, using the library lapack (the routine zgees) and the strategy described in [START_REF] Corless | A reordered Schur factorization method for zerodimensional polynomial systems with multiple roots[END_REF]. The computations are performed on an AMD-Athlon 2400+ with 256M B of main memory. We show the results obtained with our implementation in the case where the grading that we use for K[x] is the usual one. In the sequel, drvl will refer to the choice function associated to the Degree Reverse Lexicographical order, dlex to the degree lexicographical order, M ac to Macaulay's choice function (see Example 2.8), minsz to the choice function over the rational that minimizes the memory needed in the reduction loop (this choice only minimizes a local step and does not insure local minimality of the global required memory), and mix to the choice function that returns randomly either the result of minsz, or of drvl applied to its input. To analyse the quality of approximation, we mesure the maximal norm at the computed roots of the initial polynomials f i and denote it hereafter by mnacr.

Generic equations

The method we propose here is an extension of the Gröbner bases computations. As such it can compute Gröbner bases. The implementation we have is not as optimized as the Gröbner bases ones that are being worked on for decades. An important work, mostly on linear algebra, remains to be done on our program. However we want to show that the method we propose here is competitive, and that it does not lose the good practical efficiency of Gröbner bases computations [START_REF] Faugère | A new efficient algorithm for computing Gröbner Basis (F4)[END_REF]. As the arithmetic used in our programs for doing exact computation is the rational arithmetic of gmp, which is much slower than integer computations used in the other software we will restrict our-self to the use of modular arithmetic. The family of examples we have chosen is the Katsura(n)3 equations. These equations are projective complete intersection with no zero at infinity. Using the Macaulay choice function, we know apriori that Macaulay's basis will be a monomial basis of the quotient algebra, so we know, apriori, what monomials will be leading monomials for the whole computation; so in this case we can guarantee that no test to 0 returns erroneous result even using floating point arithmetic. We compare first our program to one of the best implementations available, Magma's implementation of F 4 algorithm [START_REF] Faugère | A new efficient algorithm for computing Gröbner Basis (F4)[END_REF]. Let us mention that Gb, one of the reference implementation of Buchberger's algorithm, spends 659s on Katsura [START_REF] Faugère | A new efficient algorithm for computing Gröbner Basis (F4)[END_REF].

Numerically we observe that choosing the mac function also results in a better conditioning of the computations. More precisely on Katsura(6), and using a threshold of 10 For the 64 bits computation the results computed for the drvl and dlex orders are erroneous due to roundoff errors. The time given is the time spent in the computation of the multiplication matrices. Afterward, we used either lapack to perform the eigenvector computations or Maple when we needed extended precision. Because of the different nature of these tools, we do not report on the solving part timing. Finally we show here the amount of memory needed to perform the computations over Q, using gmp mpq. On these experiments, we observe that the local strategy minsz which tends to minimize locally the size of the coefficients in the linear algebra operations, does not yield globally the optimal output size. In this example, the time and the memory size seem to be correlated.

Parallel robot

Let us consider the famous direct kinematic problem of the parallel robot4 [START_REF] Mourrain | The 40 generic positions of a parallel robot[END_REF]. First we use floating point numbers to check the numerical requirements of the computations for different orders. For testing a number to be 0, we will use a leveling (here 10 -8 is enough) and we will check afterward that the choices performed are the same as those done using modular arithmetic. This is equivalent to the use of an hybrid arithmetic [START_REF] Traverso | Numerical stability and stabilization of Gröbner basis computation[END_REF]. Here we see that choosing the right choice function can increase (but not so much in this case) the numerical accuracy of the roots. Hereafter we use the parametrization of [START_REF] Lazard | Stewart platforms and Gröbner bases[END_REF] for solving, it involves more variables, gives better timings but less correct digits on the final result. Finally we performed tests using rational arithmetic. In fact, it is not so surprising to see that the choice function γ has a big impact in terms of the computational time and of the memory required. However in this problem, the time and the memory size do not seem to be correlated as in the previous case.

We also mention here that over-constraining the system can result in a dramatic decrease of the computation time. Indeed expressing more constraints than necessary can simplify computations significantly (see [START_REF] Mourrain | Generalised normal forms and polynomial system solving[END_REF]).

Definition 2 . 7 Example 2 . 8

 2728 We say that a function γ : K[x] → M (M is the set of all monomials in the variables x 1 , . . . , x n ), is a choice function refining the grading Λ, if for any polynomial p, γ(p) is a monomial such that γ(p) ∈ supp(p), if m ∈ supp(p), m = γ(p) then γ(p) does not divide m, and Λ(γ(p)) = max{Λ(m), m ∈ supp(p)}. The coefficient of the monomial γ(p) in p will be denoted by κ(p). In the following, we consider a Macaulay 1 choice function γ, such that for all p ∈ K[x], γ(p) = x α1 1 • • • x αn n satisfies, |γ(p)| = max{|m|; m ∈ supp(p)} = d, and ∃i 0 st. α i0 = max{deg xi (m), m ∈ supp(p) and , |m| = d; i = 1, . . . , n}.

Theorem 4 . 3

 43 Let B ⊂ M be connected to 1 and let F = (f ω ) ω∈∂B be a border basis for B. Then Syz(F ) is generated by the relations (2), (3) and (4).Proof. Let σ = ω p ω e ω ∈ Syz(F ). Consider in this sum, any term λ m e θ where λ ∈ K -{0}, m ∈ M, θ ∈ ∂B and δ B (m θ) < |m| + 1. Then, there exists m

  Under these hypotheses, by Theorem 3.4, for any λ ∈ Λ, (πF ) | B + λ extends uniquely to a projection π e F λ from K[x] λ onto B λ , such that ker(π e F λ ) = F λ . Since for any λ, λ ′ ∈ Λ such that λ ≺ λ ′ , we have (B λ ′ ) λ = B λ , and F λ ⊂ (F λ ′ ) λ , we also have (π e F λ ′ ) |K[x] λ = π e F

for 1 ≤ i, j ≤ n iff there exists a unique projection π e F from K[x] onto B such that ker(π e F ) = (F ) and (π e F ) | B + = π F . Proof. λ . This defines a unique linear operator π e F on K[x] such that π e |K[x] λ = π e F λ and ker(π e F ) = λ∈Λ F λ = (F ). It proves the direct implication. The converse implication is immediate. 2

  -10 we have: -28 10 -24 10 -30 10 -20 10 -15 10 -19 --10 -11

	γ	drvl	dlex	mac	drvl	dlex	mac	drvl dlex	mac
	# bits	128	128	128	80	80	80	64	64	64
	time	1.98s	2.62s	1.64s	1.35s	3.98s	0.95s	-	-	0.9s
	mnar	10

It gives monomial basis similar to those given by Macaulay in his multivariate resultant construction[START_REF] Macaulay | Some formulae in elimination[END_REF].

http://www-sop.inria.fr/galaad/synaps/

http://www-sop.inria.fr/galaad/data/

http://www-sop.inria.fr/galaad/data/

Acknowledgments: We thank A. Quadrat for interesting discussions on differential algebra, prolongation and involutivity.