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 .
다음 줄 : 다항식을 생성합니다. 마지막을 제외한 모든 항목은 a , 로 종료되어야 합니다. 예:

 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 기지 컴퓨팅

msolve 기본 필드가 유리수 필드이거나 소수 필드인 경우(특성은 2^31보다 작아야 함) 그로브너 베이스를 계산합니다.

다음 명령

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

소위 등급 역 사전식 순서 지정을 위해 in.ms 의 입력 시스템에 의해 생성된 이상의 축소된 Groebner 기반의 주요 단항식을 계산합니다. 이를 통해 입력 다항식(기본 필드의 대수적 폐쇄에서)으로 설정된 솔루션의 차원과 이들이 생성하는 이상적인 정도를 추론할 수 있습니다.

다음과 같이 -g 2 플래그 사용

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

등급이 매겨진 역 사전 편찬 순서에 대해 축소된 Groebner 기준을 반환합니다.

msolve 하면 -e 플래그 덕분에 단일 블록 제거 단항 차수를 사용하여 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]]]
]]:

이는 수치 근사치가 (-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 의 멀티스레딩은 다음에서 사용됩니다.

• Groebner에 사용되는 선형 대수 알고리즘은 소수 필드에 대한 계산을 기반으로 합니다.
• 실수를 해결하기 위한 다중 모듈식 계산(모든 중간 및 독립 소수 계산이 병렬로 실행됨)
• 실제 루트 격리를 위한 알고리즘.

대수학의 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에서 사용됩니다.

여기와 여기를 보시면 됩니다

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의 지원을 받습니다.