# MSOLVE: Multivariate polynomial system solver 

| **Documentation**                                                       |
|:-------------------------------------------------------------------------:|
| [![][docs-stable-img]][docs-stable-url] [![][docs-dev-img]][docs-dev-url] |

[https://msolve.lip6.fr/](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](https://msolve.lip6.fr/downloads/msolve-tutorial.pdf)

Some of the functionalities of [msolve](https://msolve.lip6.fr) are already available 
in the computer algebra systems [Oscar](https://oscar-system.github.io/Oscar.jl) 
and [SageMath](https://sagemath.org). See below for some more information about 
this.

# Install Instructions

See the INSTALL file.

# Input File Format

More informations are given in the tutorial (see [https://msolve.lip6.fr](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`.<br/>
**2nd line**: field characteristic, e.g. `0`.<br/>
**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+...`.

# 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 `-v`flag 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^31).


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. 

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

For instance, on input file `in.ms` as follows
```
x, y
0
x^2+y^2-4,
x*y-1
``` 
the call `./msolve -f in.ms -o out.ms` will display in the file `out.ms` the following 
output
```
[0, [1,
[[[-41011514734338452707966945920 / 2^96, -41011514734338452707966945917 / 2^96], [-153057056683910732545430822374 / 2^96, -153057056683910732545430822373 / 2^96]], 
[[-612228226735642930181723289497 / 2^98, -612228226735642930181723289492 / 2^98], [-164046058937353810831867783675 / 2^98, -164046058937353810831867783674 / 2^98]], 
[[612228226735642930181723289492 / 2^98, 612228226735642930181723289497 / 2^98], [164046058937353810831867783674 / 2^98, 164046058937353810831867783675 / 2^98]], 
[[41011514734338452707966945917 / 2^96, 41011514734338452707966945920 / 2^96], [153057056683910732545430822373 / 2^96, 153057056683910732545430822374 / 2^96]]]
]]:
```
which are the 4 isolating boxes of the 4 exact roots whose numerical approximations are 
`(-0.5176380902, -1.931851653)`, `(-1.931851653, -0.5176380902)`, 
`(1.931851653, 0.5176380902)` and `(0.5176380902, 1.931851653)`.

# Multi-threading

Several components of `msolve` are parallelized through multi-threading. 
Typing 
```
./msolve -t 4 -f in.ms -o out.ms
```
tells `msolve` to use 4 threads. Multi-threading in `msolve` is used in 
- linear algebra algorithms used for Groebner bases computations over 
prime fields
- multi-modular computations for solving over the reals (all intermediate 
and independent prime computations are run in parallel)
- algorithms for real root isolation.

# `msolve` in [AlgebraicSolving](https://github.com/algebraic-solving/AlgebraicSolving.jl)

[AlgebraicSolving](https://github.com/algebraic-solving/AlgebraicSolving.jl) is a Julia package
that wraps `msolve` and provides some more functionality like computing rational solutions.
See [here](https://algebraic-solving.github.io/) for more information and documentation.

# `msolve` in [Oscar](https://oscar-system.github.io/Oscar.jl)

`msolve` is used in [Oscar](https://oscar-system.github.io/Oscar.jl) to *solve* 
polynomial systems with rational coefficients. 

It will detect if the input system has finitely many complex solutions, in which case 
it will output a rational parametrization of the solution set as well as the 
real solutions to the input system (see `msolve`'s 
tutorial [here](https://msolve.lip6.fr/downloads/msolve-tutorial.pdf)).

You can have a look at [this](https://github.com/oscar-system/Oscar.jl/blob/master/src/Rings/solving.jl) and the documentation of [Oscar](https://oscar-system.github.io/Oscar.jl).

Here is how you can use it.
```jldoctest
julia> R,(x1,x2,x3) = PolynomialRing(QQ, ["x1","x2","x3"])
(Multivariate Polynomial Ring in x1, x2, x3 over Rational Field, fmpq_mpoly[x1, x2, x3])
julia> I = ideal(R, [x1+2*x2+2*x3-1, x1^2+2*x2^2+2*x3^2-x1, 2*x1*x2+2*x2*x3-x2])
ideal(x1 + 2*x2 + 2*x3 - 1, x1^2 - x1 + 2*x2^2 + 2*x3^2, 2*x1*x2 + 2*x2*x3 - x2)
julia> real_solutions(I)
((84*x^4 - 40*x^3 + x^2 + x, 336*x^3 - 120*x^2 + 2*x + 1, PolyElem[-184*x^3 + 80*x^2 - 4*x - 1, -36*x^3 + 18*x^2 - 2*x], fmpz[-1, -1]), Vector{fmpq}[[744483363399261433351//1180591620717411303424, 372241681699630716673//1180591620717411303424, -154187553040555781639//1180591620717411303424], [1, 0, 0], [71793683196126133110381699745//316912650057057350374175801344, 71793683196126133110381699745//633825300114114700748351602688, 173325283664805084153412401855//633825300114114700748351602688], [196765270119568550571//590295810358705651712, 1//590295810358705651712, 196765270119568550571//590295810358705651712]])
```

# `msolve` in [SageMath](https://sagemath.org)

When you have `msolve` installed, it is used by [SageMath](https://sagemath.org) 
when you call the `Variety` function for solving polynomial systems with real 
coefficients. 

You can have a look 
[here](https://github.com/sagemath/sage/blob/develop/src/sage/rings/polynomial/msolve.py) 
and 
[here](https://github.com/sagemath/sage/blob/develop/src/sage/rings/polynomial/multi_polynomial_ideal.py) 

We are grateful to Marc Mezzarobba who initiated the usage of 
`msolve`in [SageMath](https://sagemath.org)
and the whole development team of [SageMath](https://sagemath.org), 
in particular those involed 
in this [ticket](https://trac.sagemath.org/ticket/33734)


# Citing `msolve`

If you have used `msolve` in the preparation of some paper, we are grateful that you 
cite it as follows: 
```
msolve: A Library for Solving Polynomial Systems, 
J. Berthomieu, C. Eder, M. Safey El Din, Proceedings of the  
46th International Symposium on Symbolic and Algebraic Computation (ISSAC), 
pp. 51-58, ACM, 2021.
```
or, if you use BibTeX entries: 
```
@inproceedings{msolve,
  TITLE = {{msolve: A Library for Solving Polynomial Systems}},
  AUTHOR = {Berthomieu, J{\'e}r{\'e}my and Eder, Christian and {Safey El Din}, Mohab},
  BOOKTITLE = {{2021 International Symposium on Symbolic and Algebraic Computation}},
  ADDRESS = {Saint Petersburg, Russia},
  SERIES = {46th International Symposium on Symbolic and Algebraic Computation},
  PAGES     = {51--58},
  PUBLISHER = {{ACM}},  
  YEAR = {2021},
  MONTH = Jul,
  DOI = {10.1145/3452143.3465545},
  PDF = {https://hal.sorbonne-universite.fr/hal-03191666v2/file/main.pdf},
  HAL_ID = {hal-03191666},
  HAL_VERSION = {v2},
}
```
The paper can be downloaded [here](https://hal.sorbonne-universite.fr/hal-03191666v2/file/main.pdf).

[docs-dev-img]: https://img.shields.io/badge/docs-dev-blue.svg
[docs-dev-url]: https://msolve.lip6.fr/downloads/msolve-tutorial.pdf

[docs-stable-img]: https://img.shields.io/badge/docs-stable-blue.svg
[docs-stable-url]: https://msolve.lip6.fr/downloads/msolve-tutorial.pdf

# Funding

The development of `msolve` is supported by the [Forschungsinitiative Rheinland-Pfalz](https://rptu.de/forschung/forschungsinitiative-rlp).