fgb_sage
¶
A Sage interface for FGb¶
This package is a SageMath interface to FGb and can be installed as a Python package for use with Sage. It provides a simple link between the Cinterface of FGb and polynomials and ideals in Sage.
FGb is a Clibrary by J. C. Faugère for Gröbner basis computations, with support for:
 Gröbner bases over ℚ and finite prime fields
 parallel computations (over finite fields)
 elimination/block orders (degreereverselexicographic, only)
Examples¶
See the examples and documentation at https://fgbsage.readthedocs.io.
Installation¶
Requirements: Linux with a recent version of Sage (tested with Sage 9.5.rc0 on Ubuntu 20.04 as well as with Sage 9.6 from Arch Linux).
First, clone the repository from GitHub and then compile and run the tests:
git clone https://github.com/mwageringel/fgb_sage.git && cd fgb_sage
sage setup.py test
After the tests passed successfully, run the following command to install the package for use with Sage:
sage python m pip install upgrade noindex v .
Alternatively, to install into the Python user install directory (no root access required), run:
sage python m pip install upgrade noindex v user .
Packaged versions of Sage¶
If Sage was installed by the package manager of your Linux distribution, you may need to install a few more dependencies in order to compile this package. For example, on
Arch Linux:
pacman S asdeps cython pythonpkgconfig
Ubuntu:
libgsldev liblinboxdev libsingular4dev libntldev libflintdev libmpfrdev libparidev python3ipywidgets
Alternatively, you can download a Sage binary, use Sage via Docker or install Sage from source. See also issue #2.
Issues¶
 macOS: Support for macOS has been dropped for the time being due to difficulties in
compiling this package with
fopenmp
since Sage version 8.8. Compiling the entirety of Sage with GCC support might make this work, but this was not tested. See issue #3.  Memory leaks: The underlying FGb program leaks memory, which can be a problem when computing many Gröbner bases in a single longlived process. In this case, it might be better to split the computation into several processes or use a different Gröbner basis algorithm available in Sage.
Documentation for fgb_sage
¶
This interface has two main functions:
groebner_basis()
 compute a Groebner basiseliminate()
 compute an elimination ideal

fgb_sage.
groebner_basis
(polys, **kwds)¶ Compute a Groebner basis of an ideal using FGb.
Supported term orders of the underlying polynomial ring are
degrevlex
orders, as well as block orders with twodegrevlex
blocks (elimination orders). Supported coefficient fields are QQ and finite prime fields of size up toMAX_PRIME
= 65521 < 2^16.INPUT:
polys
– an ideal or a polynomial sequence, the generators of an ideal.threads
– integer (default: 1); only seems to work in positive characteristic.force_elim
– integer (default: 0); ifforce_elim=1
, then the computation will return only the result of the elimination, if an elimination order is used.verbosity
– integer (default: 1), display progress info.matrix_bound
– integer (default: 500000); this is is the maximal size of the matrices generated by F4. This value can be increased according to available memory.max_base
– integer (default: 100000); maximum number of polynomials in output.
OUTPUT: the Groebner basis.
EXAMPLES:
This example computes a Groebner basis with respect to an elimination order:
sage: R = PolynomialRing(QQ, 5, 'x', order="degrevlex(2),degrevlex(3)") sage: I = sage.rings.ideal.Cyclic(R) sage: import fgb_sage # optional fgb_sage sage: gb = fgb_sage.groebner_basis(I) # optional fgb_sage, random ... sage: gb.is_groebner(), gb.ideal() == I # optional fgb_sage (True, True)
Over finite fields, parallel computations are supported:
sage: R = PolynomialRing(GF(fgb_sage.MAX_PRIME), 4, 'x') # optional fgb_sage sage: I = sage.rings.ideal.Katsura(R) # optional fgb_sage sage: gb = fgb_sage.groebner_basis(I, threads=2, verbosity=0) # optional fgb_sage, random sage: gb.is_groebner(), gb.ideal() == I # optional fgb_sage (True, True)
If
fgb_sage.groebner_basis()
is called with an ideal, the result is cached onMPolynomialIdeal.groebner_basis()
so that other computations on the ideal do not need to recompute a Groebner basis:sage: I.groebner_basis.is_in_cache() # optional fgb_sage True sage: I.groebner_basis() is gb # optional fgb_sage True
However, note that
gb.ideal()
returns a new ideal and, thus, does not have a Groebner basis in cache:sage: gb.ideal().groebner_basis.is_in_cache() # optional fgb_sage False
TESTS:
Check that the result is not cached if it is only a basis of an elimination ideal:
sage: R = PolynomialRing(QQ, 5, 'x', order="degrevlex(2),degrevlex(3)") sage: I = sage.rings.ideal.Cyclic(R) sage: import fgb_sage sage: gb = fgb_sage.groebner_basis(I, force_elim=1) # optional fgb_sage, random ... sage: I.groebner_basis.is_in_cache() # optional fgb_sage False

fgb_sage.
eliminate
(polys, elim_variables, **kwds)¶ Compute a Groebner basis with respect to an elimination order defined by the given variables.
INPUT:
polys
– an ideal or a polynomial sequence.elim_variables
– the variables to eliminate.force_elim
– integer (default: 1).kwds
– same as ingroebner_basis()
.
OUTPUT: a Groebner basis of the elimination ideal.
EXAMPLES:
sage: R.<x,y,t,s,z> = PolynomialRing(QQ,5) sage: I = R * [xt,yt^2,zt^3,sx+y^3] sage: import fgb_sage # optional  fgb_sage sage: gb = fgb_sage.eliminate(I, [t,s], verbosity=0) # optional  fgb_sage, random open simulation sage: gb # optional  fgb_sage [x^2  y, x*y  z, y^2  x*z] sage: gb.is_groebner() # optional  fgb_sage True sage: gb.ideal() == I.elimination_ideal([t,s]) # optional  fgb_sage True
Note
In some cases, this function fails to set the correct elimination order, see trac ticket #24981. This was fixed in Sage 8.7.

fgb_sage.
internal_version
()¶ Get the internal version of FGb.
OUTPUT: a dictionary containing the versions of FGb for
FGb_int
andFGb_modp
, characteristic 0 and positive characteristic, respectively. These versions differ between Linux and macOS.EXAMPLES:
sage: import fgb_sage # optional  fgb_sage sage: fgb_sage.internal_version() # optional  fgb_sage {'FGb_int': ..., 'FGb_modp': ...}
License¶
MIT for this package fgb_sage. However, note that FGb is licensed for academic use only.
Links¶
 FGb homepage
fgb_sage
on GitHub documentation for Gröbner bases in Sage