Download msolve - download do código-fonte msolve

msolve

Outro código-fonte

v0.7.3

Baixar

MSOLVE: Solucionador de sistema polinomial multivariado

Documentação

https://msolve.lip6.fr/

msolve é uma biblioteca C de código aberto que implementa algoritmos de álgebra computacional para resolver sistemas polinomiais (com coeficientes racionais ou coeficientes em um corpo principal).

Atualmente, com msolve , você pode basicamente resolver sistemas polinomiais multivariados. Isso inclui:

o cálculo das bases de Groebner
isolamento de raiz real das soluções para sistemas polinomiais
o cálculo da dimensão e do grau do conjunto de soluções e muitas outras coisas que você pode fazer usando o msolve.

Um tutorial está disponível aqui

Algumas das funcionalidades do msolve já estão disponíveis nos sistemas de álgebra computacional Oscar e SageMath. Veja abaixo mais algumas informações sobre isso.

Instruções de instalação

Veja o arquivo INSTALAR.

Formato do arquivo de entrada

Mais informações são fornecidas no tutorial (ver https://msolve.lip6.fr)

Os arquivos de entrada msolve precisam ter o seguinte formato:

1ª linha : variáveis como lista separada por vírgulas, por exemplo x1,x2,x3,x4,y1,y2 .
2ª linha : característica do campo, por exemplo, 0 .
seguintes linhas : gerando polinômios, todos, exceto o último, precisam terminar com a , por exemplo

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

Polinômios podem ser multilinhas, portanto , como separadores.

Os coeficientes podem ser racionais, usando / , por exemplo -2/3*x2*y1^2+... .

Uso básico

Alguns comandos básicos são os seguintes:

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

vai:

detectar se o sistema de entrada tem dimensão no máximo 0
quando o sistema tem dimensão no máximo 0 e os coeficientes são números racionais, msolve irá isolar as soluções reais
quando o sistema tem dimensão no máximo 0 e os coeficientes estão em um campo primo, msolve irá calcular uma parametrização das soluções

Todos os dados de saída são exibidos no arquivo out.ms

O sinalizador -v permite controlar o detalhamento, fornecendo informações sobre o que msolve está fazendo. Experimente isso.

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

Calculando bases de Groebner

msolve calcula bases de Groebner quando o corpo base é o corpo de números racionais ou um corpo primo (a característica deve ser menor que 2 ^ 31).

O seguinte comando

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

calculará os monômios principais da base reduzida de Groebner do ideal gerado pelo sistema de entrada em in.ms para a chamada ordenação lexicográfica reversa graduada. Isso permite deduzir a dimensão do conjunto de soluções para os polinômios de entrada (em um fechamento algébrico do corpo base), bem como o grau do ideal que eles geram.

Usando o sinalizador -g 2 da seguinte maneira

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

retornará a base de Groebner reduzida para a ordenação lexicográfica reversa graduada.

msolve também permite que você execute cálculos de bases de Groebner usando ordem monomial de eliminação de um bloco, graças ao sinalizador -e . O seguinte comando

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

realizará o cálculo da base de Groebner eliminando a primeira variável. De forma mais geral, usar -ek eliminará as primeiras k variáveis.

Resolvendo os números reais

Quando o sistema polinomial de entrada possui coeficientes racionais e quando possui um número finito de soluções complexas , msolve irá, por padrão, calcular as soluções reais para o sistema de entrada. Eles são codificados com caixas de isolamento para todas as coordenadas de todas as soluções reais.

Por exemplo, no arquivo de entrada in.ms da seguinte forma

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

a chamada ./msolve -f in.ms -o out.ms exibirá no arquivo out.ms a seguinte saída

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

que são as 4 caixas isolantes das 4 raízes exatas cujas aproximações numéricas são (-0.5176380902, -1.931851653) , (-1.931851653, -0.5176380902) , (1.931851653, 0.5176380902) e (0.5176380902, 1.931851653) .

Multithreading

Vários componentes do msolve são paralelizados por meio de multithreading. Digitando

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

diz msolve para usar 4 threads. Multi-threading em msolve é usado em

algoritmos de álgebra linear usados para cálculos de bases de Groebner sobre campos principais
cálculos multimodulares para resolver os reais (todos os cálculos primos intermediários e independentes são executados em paralelo)
algoritmos para isolamento de raiz real.

`msolve` em resolução algébrica

AlgebraicSolving é um pacote Julia que envolve msolve e fornece mais algumas funcionalidades, como computação de soluções racionais. Veja aqui para mais informações e documentação.

`msolve` no Oscar

msolve é usado no Oscar para resolver sistemas polinomiais com coeficientes racionais.

Ele detectará se o sistema de entrada tem um número finito de soluções complexas e, nesse caso, produzirá uma parametrização racional do conjunto de soluções, bem como as soluções reais para o sistema de entrada (veja o tutorial do msolve aqui).

Você pode dar uma olhada nisso e na documentação do Oscar.

Aqui está como você pode usá-lo.

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

Quando o msolve está instalado, ele é usado pelo SageMath quando você chama a função Variety para resolver sistemas polinomiais com coeficientes reais.

Você pode dar uma olhada aqui e aqui

Agradecemos a Marc Mezzarobba que iniciou o uso do msolve no SageMath e a toda a equipe de desenvolvimento do SageMath, em particular aos envolvidos neste ticket

Citando `msolve`

Se você usou msolve na preparação de algum artigo, agradecemos que você o cite da seguinte forma:

 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.

ou, se você usar entradas 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},
}

O documento pode ser baixado aqui.