README.md 9.03 KB
Newer Older
Mohab Safey El Din's avatar
Mohab Safey El Din committed
1
2
# MSOLVE: Multivariate polynomial system solver 

Mohab Safey El Din's avatar
Mohab Safey El Din committed
3
| **Documentation**                                                       |
Mohab Safey El Din's avatar
Mohab Safey El Din committed
4
5
|:-------------------------------------------------------------------------:|
| [![][docs-stable-img]][docs-stable-url] [![][docs-dev-img]][docs-dev-url] |
Mohab Safey El Din's avatar
Mohab Safey El Din committed
6

Mohab Safey El Din's avatar
fix url    
Mohab Safey El Din committed
7
[https://msolve.lip6.fr/](https://msolve.lip6.fr)
Mohab Safey El Din's avatar
Mohab Safey El Din committed
8

Mohab Safey El Din's avatar
Mohab Safey El Din committed
9
10
11
12
13
`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. 
Mohab Safey El Din's avatar
Mohab Safey El Din committed
14
15
16
17
18
19
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.

20
A tutorial is available 
Mohab Safey El Din's avatar
fix url    
Mohab Safey El Din committed
21
[here](https://msolve.lip6.fr/downloads/msolve-tutorial.pdf)
Mohab Safey El Din's avatar
Mohab Safey El Din committed
22

Mohab Safey El Din's avatar
fix url    
Mohab Safey El Din committed
23
24
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) 
Mohab Safey El Din's avatar
Mohab Safey El Din committed
25
and [SageMath](https://sagemath.org). See below for some more information about 
Mohab Safey El Din's avatar
Mohab Safey El Din committed
26
27
this.

Mohab Safey El Din's avatar
Mohab Safey El Din committed
28
29
# Install Instructions

Mohab Safey El Din's avatar
Mohab Safey El Din committed
30
See the INSTALL file.
Mohab Safey El Din's avatar
Mohab Safey El Din committed
31
32
33

# Input File Format

Mohab Safey El Din's avatar
Mohab Safey El Din committed
34
More informations are given in the tutorial (see [https://msolve.lip6.fr](https://msolve.lip6.fr))
Mohab Safey El Din's avatar
Mohab Safey El Din committed
35

Mohab Safey El Din's avatar
Mohab Safey El Din committed
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
`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+...`.
Mohab Safey El Din's avatar
Mohab Safey El Din committed
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

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

Mohab Safey El Din's avatar
Mohab Safey El Din committed
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
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

Currently, this functionality is provided when the base field is a prime one 
(characteristic should be less than 2^31). 

If the input system is with rational coefficients, the computation is performed 
modulo a randomly chosen prime. 
This allows you to obtain, with high probability, the image of the actual Groebner 
basis modulo this chosen prime, hence the dimension and the degree of the ideal generated 
by the input equations. 

The following command
Mohab Safey El Din's avatar
Mohab Safey El Din committed
86
87
88
89
90
```
./msolve -g 1 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. 
Mohab Safey El Din's avatar
Mohab Safey El Din committed
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
Using the `-g 2` flag as follows
```
./msolve -g 2 in.ms -o out.ms
```
will return the reduced Groebner basis when the base field is a prime field.

`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 in.ms -o out.ms
```
will perform the Groebner basis computation eliminating the first variable. 
More generally, using `-e k` will eliminate the `k` first variables. 

# Solving over the real numbers

Mohab Safey El Din's avatar
Mohab Safey El Din committed
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
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
```
Mohab Safey El Din's avatar
Mohab Safey El Din committed
123
[0, [1,
Mohab Safey El Din's avatar
Mohab Safey El Din committed
124
125
126
127
128
129
[[[-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]]]
]]:
```
Mohab Safey El Din's avatar
Mohab Safey El Din committed
130
131
132
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)`.
Mohab Safey El Din's avatar
Mohab Safey El Din committed
133

134
135
136
137
138
139
140
141
142
143
144
145
146
147
# 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.

Mohab Safey El Din's avatar
Mohab Safey El Din committed
148
149
150
151
152
153
154
155
156
157
158
159
# `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/msolve/msolve.jl) and the documentation of [Oscar](https://oscar-system.github.io/Oscar.jl).

Mohab Safey El Din's avatar
Mohab Safey El Din committed
160
161
162
163
164
165
166
167
168
169
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> msolve(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]])
```

Mohab Safey El Din's avatar
Mohab Safey El Din committed
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
# `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`
Mohab Safey El Din's avatar
Mohab Safey El Din committed
189
190
191
192
193
194

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  
Mohab Safey El Din's avatar
Mohab Safey El Din committed
195
196
46th International Symposium on Symbolic and Algebraic Computation (ISSAC), 
pp. 51-58, ACM, 2021.
Mohab Safey El Din's avatar
Mohab Safey El Din committed
197
198
199
200
201
202
203
204
205
```
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},
Mohab Safey El Din's avatar
Mohab Safey El Din committed
206
207
  PAGES     = {51--58},
  PUBLISHER = {{ACM}},  
Mohab Safey El Din's avatar
Mohab Safey El Din committed
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
  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 [https://hal.sorbonne-universite.fr/hal-03191666v2/file/main.pdf](here)  

[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