Solution of polynomial systems using msolve

msolve is a multivariate polynomial system solver based on Gröbner bases.

This module provide implementations of some operations on polynomial ideals based on msolve.

Note that the optional package msolve must be installed.

See also

sage.rings.polynomial.msolve.groebner_basis_degrevlex(ideal, proof=True)[source]

Compute a degrevlex Gröbner basis using msolve

EXAMPLES:

sage: from sage.rings.polynomial.msolve import groebner_basis_degrevlex

sage: R.<a,b,c> = PolynomialRing(GF(101), 3, order='lex')
sage: I = sage.rings.ideal.Katsura(R,3)
sage: gb = groebner_basis_degrevlex(I); gb # optional - msolve
[a + 2*b + 2*c - 1, b*c - 19*c^2 + 10*b + 40*c,
b^2 - 41*c^2 + 20*b - 20*c, c^3 + 28*c^2 - 37*b + 13*c]
sage: gb.universe() is R # optional - msolve
False
sage: gb.universe().term_order() # optional - msolve
Degree reverse lexicographic term order
sage: ideal(gb).transformed_basis(other_ring=R) # optional - msolve
[c^4 + 38*c^3 - 6*c^2 - 6*c, 30*c^3 + 32*c^2 + b - 14*c,
a + 2*b + 2*c - 1]

>>> from sage.all import *
>>> from sage.rings.polynomial.msolve import groebner_basis_degrevlex

>>> R = PolynomialRing(GF(Integer(101)), Integer(3), order='lex', names=('a', 'b', 'c',)); (a, b, c,) = R._first_ngens(3)
>>> I = sage.rings.ideal.Katsura(R,Integer(3))
>>> gb = groebner_basis_degrevlex(I); gb # optional - msolve
[a + 2*b + 2*c - 1, b*c - 19*c^2 + 10*b + 40*c,
b^2 - 41*c^2 + 20*b - 20*c, c^3 + 28*c^2 - 37*b + 13*c]
>>> gb.universe() is R # optional - msolve
False
>>> gb.universe().term_order() # optional - msolve
Degree reverse lexicographic term order
>>> ideal(gb).transformed_basis(other_ring=R) # optional - msolve
[c^4 + 38*c^3 - 6*c^2 - 6*c, 30*c^3 + 32*c^2 + b - 14*c,
a + 2*b + 2*c - 1]

Gröbner bases over the rationals require \(proof=False\):

sage: R.<x, y> = PolynomialRing(QQ, 2)
sage: I = Ideal([ x*y - 1, (x-2)^2 + (y-1)^2 - 1])
sage: I.groebner_basis(algorithm='msolve') # optional - msolve
Traceback (most recent call last):
...
ValueError: msolve relies on heuristics; please use proof=False
sage: I.groebner_basis(algorithm='msolve', proof=False) # optional - msolve
[x*y - 1, x^2 + y^2 - 4*x - 2*y + 4, y^3 - 2*y^2 + x + 4*y - 4]

>>> from sage.all import *
>>> R = PolynomialRing(QQ, Integer(2), names=('x', 'y',)); (x, y,) = R._first_ngens(2)
>>> I = Ideal([ x*y - Integer(1), (x-Integer(2))**Integer(2) + (y-Integer(1))**Integer(2) - Integer(1)])
>>> I.groebner_basis(algorithm='msolve') # optional - msolve
Traceback (most recent call last):
...
ValueError: msolve relies on heuristics; please use proof=False
>>> I.groebner_basis(algorithm='msolve', proof=False) # optional - msolve
[x*y - 1, x^2 + y^2 - 4*x - 2*y + 4, y^3 - 2*y^2 + x + 4*y - 4]
sage.rings.polynomial.msolve.variety(ideal, ring, proof)[source]

Compute the variety of a zero-dimensional ideal using msolve.

Part of the initial implementation was loosely based on the example interfaces available as part of msolve, with the authors’ permission.

EXAMPLES:

sage: from sage.rings.polynomial.msolve import variety
sage: p = 536870909
sage: R.<x, y> = PolynomialRing(GF(p), 2, order='lex')
sage: I = Ideal([ x*y - 1, (x-2)^2 + (y-1)^2 - 1])
sage: sorted(variety(I, GF(p^2), proof=False), key=str) # optional - msolve
[{x: 1, y: 1},
 {x: 254228855*z2 + 114981228, y: 232449571*z2 + 402714189},
 {x: 267525699, y: 473946006},
 {x: 282642054*z2 + 154363985, y: 304421338*z2 + 197081624}]

>>> from sage.all import *
>>> from sage.rings.polynomial.msolve import variety
>>> p = Integer(536870909)
>>> R = PolynomialRing(GF(p), Integer(2), order='lex', names=('x', 'y',)); (x, y,) = R._first_ngens(2)
>>> I = Ideal([ x*y - Integer(1), (x-Integer(2))**Integer(2) + (y-Integer(1))**Integer(2) - Integer(1)])
>>> sorted(variety(I, GF(p**Integer(2)), proof=False), key=str) # optional - msolve
[{x: 1, y: 1},
 {x: 254228855*z2 + 114981228, y: 232449571*z2 + 402714189},
 {x: 267525699, y: 473946006},
 {x: 282642054*z2 + 154363985, y: 304421338*z2 + 197081624}]