# 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.

sage.rings.polynomial.msolve.groebner_basis_degrevlex(ideal, proof=True)#

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]


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]

sage.rings.polynomial.msolve.variety(ideal, ring, proof)#

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}]