MSOLVE: Multivariate polynomial system solver

Documentation

https://msolve.lip6.fr/

msolve is an open source C library implementing computer algebra algorithms for solving polynomial systems (with rational coefficients or coefficients in a prime field).

Currently, with msolve, you can basically solve multivariate polynomial systems. This encompasses:

• the computation of Groebner bases
• real root isolation of the solutions to polynomial systems
• the computation of the dimension and the degree of the solution set and many other things you can do using msolve.

A tutorial is available here

Some of the functionalities of msolve are already available in the computer algebra systems Oscar and SageMath. See below for some more information about this.

Install Instructions

See the INSTALL file. At the moment, msolve does not support 32 bit architectures.

Input File Format

More informations are given in the tutorial (see https://msolve.lip6.fr)

msolve input files need to be of the following format:

1st line: variables as commata separated list, e.g. x1,x2,x3,x4,y1,y2. 2nd line: field characteristic, e.g. 0. following lines: generating polynomials, all but the last one need to terminate by a ,, e.g.

x1,x2,x3,x4,y1,y2
101
x1+x2+x3+x4,
2*y1-145*y2

Polynomials may be multiline, thus , as a separator.

Coefficients can be rational, using /, e.g. -2/3*x2*y1^2+....

In each polynomial, a single occurrence of each monomial is expected; the behaviour of msolve's parser is undefined if some monomial is repeated, as in x1+x2+x3+x4-x1.

Basic usage

Some basic commands are as follows:

./msolve -f in.ms -o out.ms

will:

• detect if the input system has dimension at most 0
• when the system has dimension at most 0 and the coefficients are rational numbers, msolve will isolate the real solutions
• when the system has dimension at most 0 and the coefficients are in a prime field, msolve will compute a parametrization of the solutions

All output data are displayed in the file out.ms

The -vflag allows you to control the verbosity, giving insight on what msolve is doing. Try this.

./msolve -v 2 -f in.ms -o out.ms

Computing Groebner bases

msolve computes Groebner bases when the base field is either the field of rational numbers or a prime field (characteristic should be less than 2^52; for characteristics of at least 2^31 only Groebner bases can be computed), or GF(16) resp. GF(256), see below.

The following command

./msolve -g 1 -f in.ms -o out.ms

will compute the leading monomials of the reduced Groebner basis of the ideal generated by the input system in in.ms for the so-called graded reverse lexicographic ordering. This allows you to deduce the dimension of the solution set to the input polynomials (in an algebraic closure of the base field) as well as the degree of the ideal they generate.

Using the -g 2 flag as follows

./msolve -g 2 -f in.ms -o out.ms

will return the reduced Groebner basis for the graded reverse lexicographic ordering.

msolve also allows you to perform Groebner bases computations using one-block elimination monomial order thanks to the -e flag. The following command

./msolve -e 1 -g 2 -f in.ms -o out.ms

will perform the Groebner basis computation eliminating the first variable. More generally, using -e k will eliminate the first k variables.

Groebner bases (options -g 1 and -g 2) can also be computed over the binary extension fields GF(16) and GF(256), the 2nd line of the input file is then 2^4 resp. 2^8 (16 resp. 256 are accepted as well). Field elements are written in hexadecimal notation as bytes: bit i is the coefficient of t^i in GF(2)[t]/(t^4+t+1) resp. GF(2)[t]/(t^8+t^4+t^3+t+1), e.g. 0x1b is t^4+t^3+t+1. Field elements have to be reduced, i.e. less than 0x10 resp. 0x100, msolve stops with an error otherwise. An integer coefficient n stands for n*1, i.e. for n modulo 2, as usual in characteristic 2. For example, 0x1b*x1^2+3*x2+x3 has the coefficients t^4+t^3+t+1, 1 and 1. The Groebner basis is printed with hexadecimal coefficients. If all coefficients lie in GF(2), e.g. if they are all integers, the Groebner basis is computed over GF(2), which is faster.

Solving over the real numbers

When the input polynomial system has rational coefficients and when it has finitely many complex solutions, msolve will, by default, compute the real solutions to the input system. Those are encoded with isolating boxes for all coordinates to all real solutions.

This is the beginning of the README. Read the rest at the original. Read the full README ↗