Unduh msolve - unduh kode sumber msolve

msolve

Kode sumber lainnya

v0.7.3

Unduh

MSOLVE: Pemecah sistem polinomial multivariat

Dokumentasi

https://msolve.lip6.fr/

msolve adalah pustaka C open source yang mengimplementasikan algoritma aljabar komputer untuk menyelesaikan sistem polinomial (dengan koefisien rasional atau koefisien dalam bidang prima).

Saat ini, dengan msolve , pada dasarnya Anda dapat menyelesaikan sistem polinomial multivariat. Ini meliputi:

perhitungan basis Groebner
isolasi akar nyata dari solusi sistem polinomial
perhitungan dimensi dan derajat himpunan solusi dan banyak hal lain yang dapat Anda lakukan menggunakan msolve.

Tutorial tersedia di sini

Beberapa fungsi msolve sudah tersedia di sistem aljabar komputer Oscar dan SageMath. Lihat di bawah untuk beberapa informasi lebih lanjut tentang ini.

Instal Petunjuk

Lihat file INSTALL.

Masukkan Format Berkas

Informasi lebih lanjut diberikan dalam tutorial (lihat https://msolve.lip6.fr)

file input msolve harus dalam format berikut:

Baris pertama : variabel sebagai daftar yang dipisahkan koma, misalnya x1,x2,x3,x4,y1,y2 .
Baris ke-2 : karakteristik bidang, misal 0 .
baris berikut : menghasilkan polinomial, semua kecuali yang terakhir harus diakhiri dengan , , misalnya

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

Polinomial bisa berupa multiline, oleh karena itu , sebagai pemisah.

Koefisien bisa rasional, menggunakan / , misalnya -2/3*x2*y1^2+... .

Penggunaan dasar

Beberapa perintah dasar adalah sebagai berikut:

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

akan:

mendeteksi apakah sistem input memiliki dimensi paling banyak 0
ketika sistem memiliki dimensi paling banyak 0 dan koefisiennya adalah bilangan rasional, msolve akan mengisolasi solusi nyata
ketika sistem memiliki dimensi paling banyak 0 dan koefisien berada dalam bidang prima, msolve akan menghitung parameterisasi solusi

Semua data keluaran ditampilkan di file out.ms

Bendera -v memungkinkan Anda mengontrol verbositas, memberikan wawasan tentang apa yang msolve sedang lakukan. Coba ini.

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

Menghitung basis Groebner

msolve menghitung basis Groebner ketika bidang dasarnya adalah bidang bilangan rasional atau bidang prima (karakteristik harus kurang dari 2^31).

Perintah berikut

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

akan menghitung monomial terdepan dari basis Groebner tereduksi dari ideal yang dihasilkan oleh sistem masukan dalam in.ms untuk apa yang disebut pengurutan leksikografis terbalik bertingkat. Hal ini memungkinkan Anda untuk menyimpulkan dimensi solusi yang ditetapkan ke polinomial masukan (dalam penutupan aljabar bidang dasar) serta derajat ideal yang dihasilkannya.

Menggunakan flag -g 2 sebagai berikut

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

akan mengembalikan basis Groebner tereduksi untuk pengurutan leksikografis terbalik bertingkat.

msolve juga memungkinkan Anda melakukan perhitungan basis Groebner menggunakan urutan monomial eliminasi satu blok berkat tanda -e . Perintah berikut

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

akan melakukan perhitungan basis Groebner dengan menghilangkan variabel pertama. Secara umum, penggunaan -ek akan menghilangkan k variabel pertama.

Menyelesaikan bilangan real

Ketika sistem polinomial masukan memiliki koefisien rasional dan memiliki banyak solusi kompleks yang berhingga , msolve akan, secara default, menghitung solusi nyata untuk sistem masukan. Itu dikodekan dengan kotak isolasi untuk semua koordinat ke semua solusi nyata.

Misalnya pada input file in.ms sebagai berikut

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

panggilan ./msolve -f in.ms -o out.ms akan menampilkan output berikut di file 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]]]
]]:

yang merupakan 4 kotak isolasi dari 4 akar eksak yang perkiraan numeriknya adalah (-0.5176380902, -1.931851653) , (-1.931851653, -0.5176380902) , (1.931851653, 0.5176380902) dan (0.5176380902, 1.931851653) .

Multi-utas

Beberapa komponen msolve diparalelkan melalui multi-threading. Mengetik

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

memberitahu msolve untuk menggunakan 4 utas. Multi-threading di msolve digunakan di

algoritma aljabar linier yang digunakan untuk Groebner mendasarkan perhitungan pada bidang prima
komputasi multi-modular untuk penyelesaian real (semua komputasi prima perantara dan independen dijalankan secara paralel)
algoritma untuk isolasi root nyata.

`msolve` di AlgebraicSolving

AlgebraicSolving adalah paket Julia yang membungkus msolve dan menyediakan lebih banyak fungsi seperti komputasi solusi rasional. Lihat di sini untuk informasi dan dokumentasi lebih lanjut.

`msolve` di Oscar

msolve digunakan di Oscar untuk menyelesaikan sistem polinomial dengan koefisien rasional.

Ini akan mendeteksi jika sistem masukan memiliki banyak solusi kompleks yang tak terhingga, dalam hal ini ia akan mengeluarkan parameterisasi rasional dari kumpulan solusi serta solusi nyata untuk sistem masukan (lihat tutorial msolve di sini).

Anda dapat melihat ini dan dokumentasi Oscar.

Inilah cara Anda dapat menggunakannya.

 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` di SageMath

Jika Anda telah menginstal msolve , ini digunakan oleh SageMath saat Anda memanggil fungsi Variety untuk menyelesaikan sistem polinomial dengan koefisien nyata.

Anda dapat melihatnya di sini dan di sini

Kami berterima kasih kepada Marc Mezzarobba yang memprakarsai penggunaan msolve di SageMath dan seluruh tim pengembangan SageMath, khususnya mereka yang terlibat dalam tiket ini

Mengutip `msolve`

Jika Anda pernah menggunakan msolve dalam penyusunan beberapa makalah, kami berterima kasih Anda mengutipnya sebagai berikut:

 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.

atau, jika Anda menggunakan entri 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},
}

Makalahnya dapat diunduh di sini.