msolve

MSOLVE：多元多项式系统求解器

文档

https://msolve.lip6.fr/

msolve是一个开源 C 库，实现用于求解多项式系统（具有有理系数或素数域中的系数）的计算机代数算法。

目前，使用msolve基本上可以求解多元多项式系统。这包括：

• Groebner 基的计算
• 多项式系统解的实根隔离
• 解集的维数和度数的计算以及使用 msolve 可以执行的许多其他操作。

此处提供了教程

msolve 的一些功能已经在计算机代数系统 Oscar 和 SageMath 中可用。有关此内容的更多信息，请参阅下文。

安装说明

请参阅安装文件。

输入文件格式

教程中提供了更多信息（请参阅 https://msolve.lip6.fr）

msolve输入文件需要采用以下格式：

第一行：变量作为逗号分隔列表，例如x1,x2,x3,x4,y1,y2 。
第二行：场特征，例如0 。
以下几行：生成多项式，除了最后一个之外的所有多项式都需要以,终止，例如

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

多项式可以是多行的， ,可以作为分隔符。

系数可以是有理数，使用/ ，例如-2/3*x2*y1^2+... 。

基本用法

一些基本命令如下：

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

将要：

• 检测输入系统的维度是否至多为 0
• 当系统维数至多为 0 并且系数为有理数时， msolve将隔离实数解
• 当系统的维数至多为 0 并且系数位于素数域时， msolve将计算解的参数化

所有输出数据都显示在文件out.ms中

-v标志允许您控制详细程度，从而深入了解msolve正在做什么。试试这个。

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

计算 Groebner 基

当基域是有理数域或素数域（特征应小于 2^31）时， msolve计算 Groebner 基。

以下命令

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

将计算由输入系统生成的理想值的简化 Groebner 基的主要单项式（以in.ms为单位），用于所谓的分级反向词典排序。这允许您推导输入多项式（在基域的代数闭包中）的解集的维数以及它们生成的理想的次数。

使用-g 2标志如下

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

将返回分级反向词典排序的简化 Groebner 基础。

得益于-e标志， msolve还允许您使用单块消除单项式顺序执行 Groebner 基计算。以下命令

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

将执行 Groebner 基础计算，消除第一个变量。更一般地，使用-ek将消除前k个变量。

求解实数

当输入多项式系统具有有理系数且具有有限多个复数解时，默认情况下， msolve将计算输入系统的实数解。这些都是用隔离框编码的，用于所有实际解决方案的所有坐标。

例如，在输入文件in.ms上如下

 x, y
0
x^2+y^2-4,
x*y-1

调用./msolve -f in.ms -o out.ms将在文件out.ms中显示以下输出

 [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]]]
]]:

这是 4 个精确根的 4 个隔离框，其数值近似值为(-0.5176380902, -1.931851653) 、 (-1.931851653, -0.5176380902) 、 (1.931851653, 0.5176380902)和(0.5176380902, 1.931851653) 。

多线程

msolve的多个组件通过多线程并行化。打字

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

告诉msolve使用 4 个线程。 msolve中的多线程用于

• Groebner 使用的线性代数算法基于素数域的计算
• 用于求解实数的多模计算（所有中间和独立素数计算都是并行运行的）
• 实根隔离算法。

代数求解中的msolve

AlgebraicSolving 是一个 Julia 包，它包装了msolve并提供了更多功能，例如计算有理解。请参阅此处了解更多信息和文档。

msolve奥斯卡

Oscar 中使用msolve来求解具有有理系数的多项式系统。

它将检测输入系统是否具有有限多个复杂解，在这种情况下，它将输出解集的合理参数化以及输入系统的真实解（请参阅此处的msolve教程）。

你可以看看这个和 Oscar 的文档。

以下是如何使用它。

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

在 SageMath 中msolve

安装msolve后，当您调用Variety函数来求解具有实数系数的多项式系统时，SageMath 会使用它。

你可以看看这里和这里

我们感谢 Marc Mezzarobba 发起在 SageMath 中使用msolve以及 SageMath 的整个开发团队，特别是参与此票证的人员

引用msolve

如果您在准备某些论文时使用过msolve ，我们非常感谢您按如下方式引用它：

 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.

或者，如果您使用 BibTeX 条目：

 @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},
}

该论文可以在这里下载。

资金

msolve的开发得到了莱茵兰-普法尔茨州研究计划的支持。