fgb_sage

Documentation Status

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 C-interface of FGb and polynomials and ideals in Sage.

FGb is a C-library 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 (degree-reverse-lexicographic, only)

Examples

See the examples and documentation at https://fgb-sage.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 --no-index -v .

Alternatively, to install into the Python user install directory (no root access required), run:

sage -python -m pip install --upgrade --no-index -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 python-pkgconfig
    
  • Ubuntu:

    libgsl-dev liblinbox-dev libsingular4-dev libntl-dev libflint-dev libmpfr-dev libpari-dev python3-ipywidgets
    

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 long-lived 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:

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 two degrevlex blocks (elimination orders). Supported coefficient fields are QQ and finite prime fields of size up to MAX_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); if force_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 on MPolynomialIdeal.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 in groebner_basis().

OUTPUT: a Groebner basis of the elimination ideal.

EXAMPLES:

sage: R.<x,y,t,s,z> = PolynomialRing(QQ,5)
sage: I = R * [x-t,y-t^2,z-t^3,s-x+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 and FGb_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.