msolve

MSOLVE: 多変量多項式システム ソルバー

ドキュメント

https://msolve.lip6.fr/

msolve多項式系 (有理係数または素体の係数) を解くためのコンピューター代数アルゴリズムを実装するオープン ソースの C ライブラリです。

現在、 msolve使用すると、基本的に多変量多項式系を解くことができます。これには以下が含まれます。

• グレブナー基底の計算
• 多項式システムの解の実根分離
• 次元と解セットの次数の計算、および msolve を使用して実行できるその他の多くのこと。

チュートリアルはここから入手できます

msolve の機能の一部は、コンピューター代数システム Oscar および SageMath ですでに利用可能です。これに関する詳細については、以下を参照してください。

インストール手順

INSTALL ファイルを参照してください。

入力ファイル形式

詳細については、チュートリアルで説明されています (https://msolve.lip6.fr を参照)。

msolve入力ファイルは次の形式である必要があります。

1 行目: カンマ区切りのリストとしての変数 (例: x1,x2,x3,x4,y1,y2 。
2 行目: フィールド特性、たとえば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

グレブナー基底の計算

msolve基底体が有理数体または素数体 (特性が 2^31 未満である必要がある) の場合に、グレブナー基底を計算します。

次のコマンド

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

は、いわゆる段階的逆辞書式順序付けのために、入力システムによってin.msで生成されたイデアルの縮小グレブナー基底の主要単項式を計算します。これにより、(基底体の代数閉包における) 入力多項式に設定された解の次元と、それらが生成する理想の次数を推定することができます。

次のように-g 2フラグを使用します

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

は、等級付けされた逆辞書編集順序の縮小グレブナー基底を返します。

msolve -eフラグのおかげで、1 ブロック消去単項次数を使用してグレブナー基底計算を実行することもできます。次のコマンド

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

最初の変数を削除するグレブナー基底計算を実行します。より一般的には、 -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]]]
]]:

これは、数値近似が(-0.5176380902, -1.931851653) 、 (-1.931851653, -0.5176380902) 、 (1.931851653, 0.5176380902)である 4 つの正確なルートの 4 つの分離ボックスであり、 (0.5176380902, 1.931851653) 。

マルチスレッド

msolveのいくつかのコンポーネントは、マルチスレッドによって並列化されます。タイピング

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

msolve 4 つのスレッドを使用するように指示します。 msolveのマルチスレッドは次のように使用されます。

• 素体上のグロブナー基底計算に使用される線形代数アルゴリズム
• 実数を解くためのマルチモジュラー計算 (すべての中間および独立した素数計算は並列実行されます)
• 実際のルート分離のためのアルゴリズム。

代数解決におけるmsolve

AlgebraicSolving は、 msolveをラップし、有理解の計算などの追加機能を提供する Julia パッケージです。詳細とドキュメントについては、ここを参照してください。

オスカーのmsolve

msolve有理係数を使用して多項式系を解くために Oscar で使用されます。

入力システムに有限個の複雑な解があるかどうかを検出します。その場合、解セットの合理的なパラメータ化と実際の解を入力システムに出力します ( 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 によって msolve が使用されます。

こことここで見ることができます

SageMath でmsolveの使用を開始した Marc Mezzarobba と、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の開発は、Forschungsinitiative Rheinland-Pfalz によってサポートされています。