Tutorial FGb through its Maple Interface

This tutorial can also be downloaded as a pdf file.

FGb is a C library for computing Gröbner bases and polynomial system solving with algebraic computations. FGb is freely distributed for academic use only. It can be used as a C library through a C program or through its interface with the Maple computer algebra system. Most of the functions are available for these two usage modes.

This tutorial presents FGb through its Maple interface. The various functionalities compute Gröbner bases or related objects which are useful for solving polynomial systems with algebraic methods (symbolic computation). The structure of the library is described in [4].

Most of the functions provided by FGb are based on the state-of-the-art algorithms for Gröbner bases such as the F₄ and F₅ algorithms [2, 3]. These algorithms are based on linear algebra routines which are given in [5]: coefficients of the polynomials are stored in row vectors according to a monomial ordering ; matrices are formed by taking such row vectors obtained by multiplying the input polynomials with monomials up to some degree and performing row echelon form computations.

In order to use FGb, it is not necessary to know more about Gröbner bases and monomial orderings than the few lines below. However for an expert usage, learning about such notions is really useful: such knowledge is crucial to know how to use efficiently these functions. The interested reader can refer to [1, Chapter 2].

The main monomial orderings provided by FGb are the degree reverse lexicographical ordering (denoted by DRL(vars)) and an elimination ordering DRL(vars1) > DRL(vars2) (here we mean that variables in vars1 are eliminated). You can use FGb without knowing the definition of the DRL-ordering. Gröbner bases are special families of polynomials that generate the same ideal (i.e. set of algebraic combinations) of the input polynomials. Their special properties allow to extract various useful information about the solution set of the input polynomial system except a description of the projection of the solution set on the space spanned by a subset of the input variables.

For this latter task, you may use the aforementioned elimination ordering: eliminating some variables leads to compute the projection on the space spanned by the other variables. In the (common) case where the solution set (in some algebraic closure) is finite, special change of ordering algorithms are used [7, 6].

Contents

• 1  Getting started
  • 1.1  Finitely many solutions.
  • 1.2  Infinitely many solutions.
• 2  Installation instructions
• 3  Basic commands
  • 3.1  fgb_gbasis(F,char,vars1,vars2,opts)
  • 3.2  fgb_gbasis_lm(F,char,vars1,vars2,opts)
  • 3.3  fgb_gbasis_elim(F,char,vars1,vars2,opts)
  • 3.4  fgb_hilbert(gb,char,vars1,vars2,v)
  • 3.5  fgb_interface()
  • 3.6  fgb_matrixn_radical(F,char,vars,num,opts)
  • 3.7  pseudo_fgb_normalForm(gb,F,char,vars1,vars2)
• 4  Advanced usage
  • 4.1  Options
  • 4.2  Advanced functions
  • 4.3  fgb_multi(F1,F2,vars1,vars2,vars3,opts)
  • 4.4  fgb_matrixn_radical2(F1,F2,char,vars1,vars2,num,opts)
  • 4.5  fgb_matrixn(F,char,vars,opts)

1  Getting started

The package FGb must be loaded in your maple session with the following command.

All FGb commands available through its Maple interface appear. These commands provide functionalities to solve polynomial systems with coefficients in a field K through Gröbner bases computations.

The fields which are supported are the prime fields ℤ/pℤ with p<2¹⁶ or the field ℚ of rational numbers.

The first task that FGb allows to tackle is the following: given a polynomial system F with coefficients in a field K as above, decide if it has solutions in the algberaic closure of K. To do that, we compute a Gröbner basis using the main function of the FGb package which is fgb_gbasis. The Gröbner basis is [1] if and only if there is no solution in the algebraic closure.

We deduce from the above computations that the system F has solutions (in ℂ and in the algebraic closure of ℤ/65521ℤ). Let us now consider the intersection of the complex solutions of F and the hyperplane defined by x+2y+3z+4t−5 and check if it has solutions.

We deduce that this intersection is empty over ℂ. The same conclusion holds over the algebraic closure of ℤ/65521ℤ.

We continue this section with additional examples. All of them can be found in maple files of the directory examples provided with the distribution of FGb.

1.1  Finitely many solutions.

Let us see how to check if a given polynomial system has a finite number of complex solutions.

When the complex solution set is finite (which is the case here), one may want to get the number of solutions (counted with multiplicities). This is done again using the output of hilb

Let p be a prime number. It is remarkable that for any choice of p outside a finite subset of the set of prime numbers, running the above computations in the field ℤ/pℤ yields the dimension and degree estimates. This is very useful for large examples since computations in ℤ/pℤ are much faster when the size of p is less than the word machine. This is what we do below with p=65521.

In the above example, the polynomial system has a finite number of complex solutions. This can be seen on the Gröbner basis: the set of leading monomials of the polynomials in the Gröbner basis contains pure powers of all variables.

For large examples, it is not so easy to extract these leading monomials of the polynomials in the Gröbner basis. The function fgb_gbasis_lm is useful because it makes this easy. Besides, the leading monomials in the basis are the only ones we really need to run fgb_hilbert.

At this point, we know that the above system F has finitely many complex solutions and we know how to count the number of complex solutions (with multiplicities). To go further we may want to know what is the projection of the solution set of F on the x-axis. Hence we want to compute a polynomial in ℚ[x] This is done by eliminating the variables y and z using the function fgb_gbasis_elim.

Finally, we may want a nice representation of this complex solution set in terms of univariate polynomials. More precisely, we would like to express the z- and y-coordinates with respect to the z-coordinates of the complex solution set. This is done with the function fgb_matrixn.

On this example, the concrete output is [ 6940480*z−56720*x⁷+25352*x⁶+12756*x⁵−14940*x⁴+5626*x³− 936*x²+32*x+5, 13880960*y−1343680*x⁷+1848208*x⁶−1016328*x⁵+284036*x⁴− 42824*x³+3676*x²−222*x+9, 3470240*x⁸−4582784*x⁷+2519968*x⁶−750640*x⁵+139000*x⁴− 19216*x³+2202*x²−146*x+1 ]

We set below c₁=6940480, c₂=13880960

and

Note that q₃ has degree 8 which is the number of complex solutions counted with multiplicities found using fgb_hilbert.

This output must me interpreted as follows: the complex solution is defined by the following representation

where q₀=∂ q₃/∂ x/deg(q₃). Note that isolating the roots of q₃ with sufficient accuracy allows to isolate the roots of the system.

1.2  Infinitely many solutions.

We focus now on what can be done for systems with infinitely many complex solutions; in this case, one says that the system has positive dimension. The following commands which, as above, use fgb_hilbert allow to compute the dimension d and the degree of the ideal generated a given polynomial system.

The above degree is the number of points counted with multiplicity obtained when augmenting the polynomial system with d generically chosen linear forms.

As aleady mentioned, when running all the above computatations over a prime field ℤ/pℤ for a prime p chosen after a finite subset of prime numbers.

Eliminating variables is useful in positive dimension: it allows to compute a subset of polynomials which define, up to taking closure, the projection of the complex solution on the space of the remaining variable. Elimination orderings are crucial for this operation.

Note that in the above example, one can extract expressions of u,v,w with respect to x,y by looking at the polynomials which depend only on w,x,y, v,x,y and u,x,y (they have degree 1 in w, v and u respectively). This is not always true but rather common.

Note also when one wants to compute only the projection and when computations are performed over ℚ, it is faster to use fgb_gbasis_elim.

This function can be used for the implicitization of curves or surfaces:

Though the runtime for the above call is less than a second on a modern computer, its output is too large to be printed here: one polynomial of degree 12 with 169 monomials.

Using fgb_gbasis with an elimination ordering for the implicitization problem is not appropriate: since it computes the whole Gröbner basis, the runtime is much larger than the one of fgb_gbasis_elim.

2  Installation instructions

 FGb: 0.00 sec 2 polys
FGb: 0.00 sec Maple: 0.05 sec

3  Basic commands

3.1  fgb_gbasis(F,char,vars1,vars2,opts)

Input description.

• F is a list of multivariate polynomials ;
• char is a natural number indicating the characteristic of the ground field; for computations over the rationals, char is 0 ;

  If char is 0 computations are performed over ℚ else they are performed over ℤ/ charℤ.

• vars1 is a list of variables (vars1 may be empty);
• vars2 is a list of variables ;
• opts is an optional argument (see Section 4).

Assumptions.

• F has either rational coefficients or coefficients in a prime field of characteristic <2¹⁶ ;
• All variables in F should appear either in vars1 or in vars2 (else an error is raised) ;
• vars1 and vars2 must have an empty intersection.

Output description. The command returns a Gröbner basis of the ideal generated by F with respect to the elimination ordering DRL(vars1)>DRL(vars2).

Examples

3.2  fgb_gbasis_lm(F,char,vars1,vars2,opts)

Input description.

• F is a list of multivariate polynomials ;
• char is a natural number indicating the characteristic of the ground field; for computations over the rationals, char is 0 ;

  If char is 0 computations are performed over ℚ else they are performed over ℤ/ charℤ.

• vars1 is a list of variables ;
• vars2 is a list of variables ;
• opts is an optional argument (see Section 4).

Assumptions.

• F has either rational coefficients or coefficients in a prime field of characteristic <2¹⁶ ;
• All variables in F should appear either in vars1 or in vars2 (else an error is raised) ;
• vars1 and vars2 must have an empty intersection.

Output description. The command returns a list of two elements [ gb, lm] where

• gb is a Gröbner basis of the ideal generated by F with respect to the elimination ordering DRL(vars1)>DRL(vars2).
• lm is the list of leading monomials of the polynomials in gb

Examples

3.3  fgb_gbasis_elim(F,char,vars1,vars2,opts)

Input description.

• F is a list of multivariate polynomials ;
• char is a natural number indicating the characteristic of the ground field; for computations over the rationals, char is 0 ;

  If char is 0 computations are performed over ℚ else they are performed over ℤ/ charℤ.

• vars1 is a list of variables ;
• vars2 is a list of variables ;
• opts is an optional argument (see Section 4).

Assumptions.

• F has either rational coefficients or coefficients in a prime field of characteristic <2¹⁶ ;
• All variables in F should appear either in vars1 or in vars2 (else an error is raised) ;
• vars1 and vars2 must have an empty intersection.

Output description. The command returns a Gröbner basis with respect to the ordering DRL( vars2) of the ideal obtained by eliminating vars1 from the one generated by F.

Examples

3.4  fgb_hilbert(gb,char,vars1,vars2,v)

Input description.

• gb is a list of polynomials ;
• char is a natural number indicating the characteristic of the ground field; for computations over the rationals, char is 0 ;

  If char is 0 computations are performed over ℚ else they are performed over ℤ/ charℤ.

• vars1 is a list of variables ;
• vars2 is a list of variables ;
• v is an used variable.

Assumptions.

• char is the charactistic of the field over which gb has been computed (char is 0 when rational coefficients have been used, else it is a prime field of characteristic <2¹⁶) ;
• gb is a Gröbner basis with respect to the ordering DRL(vars1)>DRL(vars2) ;
• v is an used variable.

Output description. The command returns a list of two elements

• the first one is a univariate polynomial P which is the Hilbert polynomial of the ideal generated by gb ;
• the second one is a natural integer dim which is the dimension of the ideal gb.

Note that, as a consequence, the Hilbert series of the ideal generated by gb is given by P/(1− v) ^dim.

Examples

3.5  fgb_interface()

Input description. This function rakes no argument

Output description. It returns a list of 5 elements as follows:

• an integer giving the maple release number ;
• a string giving the operating system ;
• an expression "FGb_modp" = <number> where <number> gives the build number of FGb_modp.
• an expression "FGb_INT" = <number> where <number> gives the build number of FGb_INT.
• an integer giving the FGb maple interface release number.

Examples

3.6  fgb_matrixn_radical(F,char,vars,num,opts)

Input description.

• F is a list of multivariate polynomials ;
• char is a natural number indicating the characteristic of the ground field; for computations over the rationals, char is 0 ;

  If char is 0 computations are performed over ℚ else they are performed over ℤ/ charℤ.

• vars is a list of variables ;
• num is a natural number ;
• opts is an optional argument (see Section 4).

Assumptions.

• F has either rational coefficients or coefficients in a prime field of characteristic <2¹⁶ ;
• vars is the list of variables appearing in F.

The assumptions below are satisfied in generic coordinates (i.e. they are true up to substituting the last variable with a random linear combination of vars) and checked by the function.

• The solution set Z of F (in the algebraic closure) is finite ;
• The set of polynomials that vanish on Z is in the so-called shape lemma position, i.e. for the lexicographical ordering, the Gröbner basis has the following form:

  vars[1]−t1( vars[n]),  vars[2]−t2( vars[n]),…,   vars[n−1]−tn−1( vars[n]),tn( vars[n]).

• Another technical assumption is requested on the DRL-Gröbner basis of the set of polynomials that vanish on Z (see [6]).

Output description. A list of polynomials of the form

where the c_i’s are coefficients and the q_i’s are univariate polynomials in vars[n]. These polynomials describe the set Z′ defined by

where q₀=∂ q_n/∂ vars[n]/deg(q_n).

When num is 0, Z′ equals Z, else Z′ is the set of points of multiplicity num in Z.

Examples

3.7  pseudo_fgb_normalForm(gb,F,char,vars1,vars2)

Input description.

• gb is a list of polynomials ;
• F is a list of multivariate polynomials ;
• char is a natural number indicating the characteristic of the ground field; for computations over the rationals, char is 0 ;

  If char is 0 computations are performed over ℚ else they are performed over ℤ/ charℤ.

• vars1 is a list of variables ;
• vars2 is a list of variables ;

Assumptions.

• gb and F have either rational coefficients or coefficients in a prime field of characteristic <2¹⁶ ;
• All variables in gb and F should appear either in vars1 or in vars2 (else an error is raised) ;
• vars1 and vars2 must have an empty intersection.
• gb is a Gröbner basis with respect to the ordering DRL(vars1)>DRL(vars2).

Output description. A list of the form

where k is the cardinality of F the c_i’s are coefficients and the p_i’s are polynomials such that p_i is the normal form of c_i f_i (where f_i is the i-th element of F.

Examples

4  Advanced usage

We describe now options, given as elements of a set, that are available for fgb_gbasis, fgb_gbasis_lm, fgb_gbasis_elim and fgb_matrixn_radical and more advanced functions for expert users.

4.1  Options

Options are given as a set of the following form

where <string_i> is a string and <num_i> is a natural number.

Verbosity : “verb”=<num>.

 
Here <num> is an integer in {0,1,2,3} and it controls the verbosity of FGb. Its default value is 0.

Informations that are printed are related to the size of the matrices appearing during the Gröbner bases reconstructions, progress in linear algebra routines (for Gröbner bases computations and algorithms for change of orderings) and rational reconstruction.

Size of matrices : “index”=<num>.

 
Recall that algorithms for Gröbner bases in FGb are based on row echelon form computations. The default limit value for the number of rows/columns matrices generated by FGb is limited to 500 000.

That may not be sufficient for very large computations and the user can increase this value (up to the limit of the available memory on its computer). Note also that increasing this value when it is not necessary may slow down the run time of FGb.

Degree restrictions : “verb”=<num>.

 
Recall also that algorithms for computations of Gröbner bases in FGb are performed by increasing degree until the requested Gröbner basis is obtained.

One can limit the degree up to which the computations are run. The limit degree is instantiated to the integer <num>.

Example:

4.2  Advanced functions

4.3  fgb_multi(F1,F2,vars1,vars2,vars3,opts)

Input description.

• F1 and F2 are lists of multivariate polynomials with rational coefficients ;
• vars1, vars2 and vars3 are lists of variables ;
• num is a natural number ;
• opts is an optional argument (see Section 4).

Assumptions.

• F1 and F2 have either rational coefficients or coefficients in a prime field of characteristic <2¹⁶ ;
• All variables appearing in F1 or F2 must appear in either vars1 or vars2 ;
• vars1 is the list of variables appearing in F2 ;
• vars1 and vars2 must have an empty intersection.

Output description. This function simulates the following sequence of computations provided that all assumptions for fgb_matrix_radical are satisfied by the system newF below.

The function returns gb.

Examples

4.4  fgb_matrixn_radical2(F1,F2,char,vars1,vars2,num,opts)

Input description.

• F1 and F2 are lists of multivariate polynomials ;
• char is a natural number indicating the characteristic of the ground field; for computations over the rationals, char is 0 ;

  If char is 0 computations are performed over ℚ else they are performed over ℤ/ charℤ.

• vars1 and vars2 are lists of variables ;
• num is a natural number ;
• opts is an optional argument (see Section 4).

Assumptions.

• F1 and F2 have either rational coefficients or coefficients in a prime field of characteristic <2¹⁶ ;
• All variables appearing in F1 or F2 must appear in either vars1 or vars2 ;
• vars1 is the list of variables appearing in F2 ;
• vars1 and vars2 must have an empty intersection.

Output description. This function simulates the following sequence of computations provided that all assumptions for fgb_matrix_radical are satisfied by the system newF below.

The function returns param.

Examples

4.5  fgb_matrixn(F,char,vars,opts)

Input description.

• F is a list of multivariate polynomials ;
• char is a natural number indicating the characteristic of the ground field; for computations over the rationals, char is 0 ;

  If char is 0 computations are performed over ℚ else they are performed over ℤ/ charℤ.

• vars is a list of variables ;
• num is a natural number ;
• opts is an optional argument (see Section 4).

Assumptions.

• F has either rational coefficients or coefficients in a prime field of characteristic <2¹⁶ ;
• vars is the list of variables appearing in F.

The assumptions below are satisfied in generic coordinates (i.e. they are true up to substituting the last variable with a random linear combination of vars) and checked by the function.

• The solution set Z of F (in the algebraic closure) is finite ;
• The set of polynomials that vanish on Z is in the so-called shape lemma position, i.e. for the lexicographical ordering, the Gröbner basis has the following form:

  vars[1]−t1( vars[n]),  vars[2]−t2( vars[n]),…,   vars[n−1]−tn−1( vars[n]),tn( vars[n]).

• Another technical assumption is requested on the DRL-Gröbner basis of the set of polynomials that vanish on Z (see [6]).

Output description. A list of polynomials of the form

where the c_i’s are coefficients and the q_i’s are univariate polynomials in vars[n]. These polynomials describe the set Z′ defined by

where q₀=∂ q_n/∂ vars[n]/deg(q_n); hence when there is no multiple root for F, Z=Z′.

Examples

References

[1]

D. Cox, J. Little, and D. O’Shea. Ideals, varieties, and algorithms, volume 3. Springer, 1992.

[2]

J.-C. Faugère. A new efficient algorithm for computing Gröbner bases (F4).-. Journal of Pure and Applied Algebra, 139(1–3):61–88, 1999.

[3]

J.-C. Faugère. A new efficient algorithm for computing Gröbner without reduction to zero (F5). In Proceedings of ISSAC 2002, pages 75 – 83. ACM Press, 2002.

[4]

J.-C. Faugère. FGb: A Library for Computing Gröbner Bases. In Komei Fukuda, Joris Hoeven, Michael Joswig, and Nobuki Takayama, editors, Mathematical Software - ICMS 2010, volume 6327 of Lecture Notes in Computer Science, pages 84–87, Berlin, Heidelberg, September 2010. Springer Berlin / Heidelberg.

[5]

J.-C. Faugère and S. Lachartre. Parallel Gaussian Elimination for Gröbner bases computations in finite fields. In M. Moreno-Maza and J.L. Roch, editors, Proceedings of the 4th International Workshop on Parallel and Symbolic Computation, PASCO ’10, pages 89–97, New York, NY, USA, July 2010. ACM.

[6]

J.-C. Faugère and C. Mou. Fast Algorithm for Change of Ordering of Zero-dimensional Gröbner Bases with Sparse Multiplication Matrices. In Proceedings of the 36th international symposium on Symbolic and algebraic computation, ISSAC ’11, pages 115–122, New York, NY, USA, 2011. ACM.

[7]

J.C. Faugère, P. Gianni, D. Lazard, and T. Mora. Efficient computation of zero-dimensional Gröbner bases by change of ordering. Journal of Symbolic Computation, 16(4):329–344, 1993.