Bases de Gröbner — Les-mathematiques.net The most powerful custom community solution in the world

Bases de Gröbner

Bonjour, 

Est-ce que quelqu'un ici connaît les bases de Gröbner et sait les obtenir avec un ordinateur (avec Sage par exemple) ? J'ai essayé de reproduire les résultats de ce document et je ne trouve pas pareil. Il s'agit de l'exemple 5. Et si quelqu'un connaît, j'ai des questions.
«1

Réponses

  • Modifié (July 2023)
    Bonjour,
    je ne saurais répondre à tes questions mais ce domaine m’intéresse aussi. Es-tu allé voir sur le site de SAGE par exemple ?
    Il semble efficace pour le calcul des bases de Gröbner.
  • Modifié (July 2023)
    Non je l'ai implémenté dans R et je souhaite utiliser ça. On peut utiliser SAGE sur leur site ?
    Sinon j'ai trouvé une librairie Pyhton sur Github mais je ne sais pas comment faire pour l'installer.
  • Et regardez ça. A l'aide d'une base de Gröbner, le gars a transformé une équation paramétrique en équation implicite. Vous y comprenez quelque chose ? Cela m'intéresse beaucoup.
  • Modifié (July 2023)
    Cet exemple :

    Je trouve bien ces deux polynômes. Mais dans le premier document que j'ai lu, l'auteur inclut aussi les deux polynômes originaux dans la base. Je suis sa méthode et donc j'ai quatre polynômes moi. Pourquoi ils ne sont pas inclus ici ? Il y en a des redondants ?
  • Modifié (July 2023)
    sage: R.<x1, x2> = PolynomialRing(QQ,2,order="deglex")
    sage: I = R.ideal([x1^3-2*x1*x2, x1^2*x2-2*x2^2+x1])
    sage: I.groebner_basis(algorithm="toy:buchberger")
    [x1^3 - 2*x1*x2, x1^2*x2 - 2*x2^2 + x1, x1^2, x1*x2, x2^2 - 1/2*x1]
  • Ah ok ça dépend de l'algo. Merci. Mais c'est bizarre non, que pour un truc engendré par deux éléments, on trouve une base à quatre éléments ? Enfin je n'y connais rien, et puis j'ai oublié l'algèbre de base.
  • Je trouve presque la même chose, j'ai juste un polynôme en plus dans la base. J'utilise l'ordre lexicographique $x>y>z$.
  • Ça peut aussi venir de l'ordre : lex contre deglex ?
    En tout cas, en effet, le nombre de polynômes dans une base de Gröbner n'est pas directement lié à une notion de dimension en général et il ne dépend pas seulement de l'idéal (i.e. un idéal a des bases de Gröbner de cardinaux différents).
  • Ah peut-être. Tu peux essayer avec lex stp? Je trouve x2^3 en plus.
  • Modifié (July 2023)
    Tadaa !
    sage: R.<x1, x2> = PolynomialRing(QQ,2,order="lex")
    sage: I = R.ideal([x1^3-2*x1*x2, x1^2*x2-2*x2^2+x1])
    sage: I.groebner_basis(algorithm="toy:buchberger")
    [x1^3 - 2*x1*x2, x1^2*x2 + x1 - 2*x2^2, x1^2, x1*x2, x1 - 2*x2^2, x2^3]
  • Génial, c'est ça que j'obtiens, merci ! 
  • J'ai ajouté cet algo à ma librairie de polynômes à coefficients dans $\mathbb{Q}$  B)

    Vous n'auriez pas une petite application ?
  • Il y en a plein dans Cox, David A.; Little, John; O'Shea, Donal (1997). Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra. Springer. ISBN 0-387-94680-2.
  • Ok merci, je vais essayer de me procurer ce livre.
  • Modifié (July 2023)
    Il y a un truc qui m'interpelle dans mon algo. Selon certaines sources, c'est cela l'algo de Buchberger:

    Or, moi je ne fais pas tout à fait ça. La différence, c'est que dès que je trouve un $S \neq 0$, je grossis $G$ en $G \cup \{S\}$ et je travaille tout de suite avec ce $G$ grossi pour les paires $\{p, q\}$ suivantes. L'auteur d'un article a détaillé l'algo sur un exemple et c'est ce qu'il fait, c'est pour ça que j'ai fait comme ça. Alors que dans l'algo ci-dessous, on finit la boucle sur $G'$ avant de passer à $G$. Est-ce correct de procéder comme je fais ? 

    PS: comment réduire une image sur le phorum ?
    [Dimensionner une image https://les-mathematiques.net/vanilla/index.php?p=/discussion/comment/2435940/#Comment_2435940 AD]
  • @Math Coss Quand tu auras 5 minutes, stp est-ce que tu peux refaire l'exemple précédent et demander la base réduite à SAGE ? J'ai implémenté "la" base minimale pour l'instant, et je trouve $-2y^2 + x$ et $4y^3$. Donc la base réduite devrait être $y^2 - \frac x2$ et $y^3$.
  • $y^2$ divise $y^3$, je ne comprends pas pourquoi mon algo n'a pas dégagé $-2y^2 + x$... d'un autre côté je ne serais pas satisfait si je trouvais une base constituée d'un seul polynôme... je retourne bosser mon algo.
  • Ah non, $x$ domine $y^2$ avec lex  :) Ca devrait être bon.
  • Sage trouve à peu près ce que tu veux par défaut.
    sage: R.<x1,x2> = PolynomialRing(QQ,2,order="lex")
    sage: I = R.ideal([x1^3-2*x1*x2, x1^2*x2-2*x2^2+x1])
    sage: I.groebner_basis()
    [x1 - 2*x2^2, x2^3]
  • C'est ça !! Génialissime. Reste à implémenter la base réduite  :p
  • Les sources de Sage sont libres... mais pourquoi ne pas utiliser Sage ?
  • Modifié (July 2023)
    Mon PC perso est mort, j'utilise celui du boulot, je ne peux pas installer Sage, à moins qu'il existe une version portable pour Windows ?

    J'ai implémenté la base réduite, peux-tu tester cet exemple stp : 

    R.<x, y, z> = PolynomialRing(QQ, 3, order = "lex")
    I = R.ideal([x^2 + y + z^2 - 1, x^2 + y + z - 1, x + y^2 + z - 1])
    I.groebner_basis()
    Je trouve ceci : 

    - base minimale (pas unique) : $P_1 = z + y^2 + x - 1, P_2 = z^2 - z, P_3 = -z + 2y^2z + y^4 + y + z^2 - 2y^2$

    - la base réduite : $P_1, P_2, -2y^2 + y + y^4 + 2*y^2z$

    Sage donne la réduite par défaut. Si ma réduite est correcte, la minimale devrait l'être aussi, vu que je construis la réduite à partir de la minimale.
  • SAGE online !!! Je vais tester ça de suite.

    Pour windows j'ai regardé, il faut installer un émulateur Linux avec les droits admin.
  • J'ai lancé l'exemple sur SAGE online, ma réduite est correcte !!!
  • @AD > C'est bizarre, moi je n'obtiens pas le cadre et les trucs interactifs pour redimensionner l'image. Il y a un autre truc je pense : en mode HTML on peut changer les dimensions.
  • Modifié (July 2023)
    @Math Coss> J'ai pris une courbe sphérique paramétrisée, je l'ai passée à elimination_ideal dans Sage. Il m'a sorti six équations. La première est celle de la sphère. J'ai pris la deuxième et j'ai obtenu ce que je voulais : une surface dont l'intersection avec la sphère est précisément cette courbe sphérique :



    Le truc c'est qu'avec ça, je suis capable de colorier de deux couleurs différentes les deux régions de la sphère séparées par la courbe, alors qu'avec seulement la paramétrisation de la courbe je ne sais pas faire ça.
  • Trois équations si je n'oublie pas une relation. La première est celle de la sphère. La deuxième et la troisième définissent la même surface. 
  • Mazette, j'ai lancé mon bazar pour obtenir une équation implicite de la surface d'Enneper, ça tourne depuis 30 minutes et ce n'est pas encore fini... Le résultat doit être un polynôme de degré 9.
  • Modifié (July 2023)
    Math Coss a dit :
    Les sources de Sage sont libres... mais pourquoi ne pas utiliser Sage ?
    Sage n'a pas vraiment de code en propre pour les bases de Groebner, à part pour faire un peu joujou (toy). En-dehors du joujou, Sage appelle Singular ou Giac (le moteur de calcul de Xcas), dont les implémentations efficaces ont nécessité plusieurs années de travail. Ce sont tous les deux des logiciels écrits en C/C++, disponibles sous forme de librairies, donc en principe linkables avec R (qui est lui-même écrit en C), et c'est certainement vers cela qu'il faut s'orienter pour utiliser des bases de Groebner ou de l'élimination directement dans R (inversement ce serait d'ailleurs intéressant de pouvoir utiliser la librairie C de R depuis Giac, j'espère un jour avoir le temps de le faire). L'intérêt d'utiliser une librairie C/C++ c'est aussi qu'on n'utilise que ce qui est nécessaire (c'est plus sobre!).
    Sinon, pour tester des bases de Groebner, vous pouvez utiliser Xcas pour Firefox, qui présente l'avantage de calculer en local, sans avoir besoin de faire des calculs à distance et d'échanger des données sur le réseau (une fois la page téléchargée), c'est plus sobre! Voici un exemple très simple d'utilisation de gbasis (pour éliminer la commande s'appelle eliminate) avec l'ordre revlex (qui est le plus efficace) et l'ordre lexicographique
  • Merci Parisse.

    Mon prog tourne encore, ça fait deux heures. Je me demande si je n'ai pas une boucle infinie en cours... :neutral:
  • Bon j'ai arrêté le bousin, ça ne finissait pas. Puis j'ai grandement amélioré mon code et il va plus vite, mon algo faisait des calculs pour du vent. Mais en fait, c'est la division qui est super lente, ça je n'y ai rien changé, je vais devoir me taper du C++ je crois.
  • Du C suffit je pense. Il faut savoir appeler une fonction C en R. Avec giac le plus simple est de convertir les données R en une chaine de caractères contenant la commande gbasis avec ses arguments, puis utiliser la fonction caseval de giac dont le prototype C est
    const char * caseval(const char *)
    puis donner à manger la chaine renvoyée à l'interpréteur de R, sans doute après l'avoir modifiée (par exemple les délimiteurs [] et le séparateur ,). 
    caseval est déclarée comme une fonction avec linkage C (extern "C").
  • Modifié (July 2023)
    Pour la surface d'Enneper, c'est un problème d'implémentation parce que c'est immédiat avec Sage (qui sous-traite).
    sage: R. = PolynomialRing(QQ,5)
    sage: I = R.ideal([-x+u-u^3/3+u*v^2, -y+v-v^3/3+v*u^2, -z+u^2-v^2])
    sage: J = I.elimination_ideal([u,v])
    sage: J
    Ideal (64*z^9 - 432*x^2*z^6 + 432*y^2*z^6 - 1215*x^4*z^3 - 6318*x^2*y^2*z^3 - 1215*y^4*z^3 - 3888*x^2*z^5 - 3888*y^2*z^5 - 1152*z^7 - 729*x^6 + 2187*x^4*y^2 - 2187*x^2*y^4 + 729*y^6 - 4374*x^4*z^2 + 4374*y^4*z^2 - 6480*x^2*z^4 + 6480*y^2*z^4 + 729*x^4*z - 1458*x^2*y^2*z + 729*y^4*z + 3888*x^2*z^3 + 3888*y^2*z^3 + 5184*z^5) of Multivariate Polynomial Ring in x, y, z, u, v over Rational Field
  • Oui j'ai essayé avec Sage. Quasi-immédiat.

    Je ne cesse d'améliorer mon code mais ça coince encore.
  • Modifié (July 2023)
    Merci Parisse. Il y a déjà du C++ dans mon code. De nos jours, avec le package Rcpp, c'est beaucoup simple de faire du C++ dans R que du C.
    Je vais regarder les librairies dont tu parles.
  • Bon, je vais fignoler mes améliorations et je vais laisser ça comme ça. Ce n'est pas en quelques jours que je referai l'implémentation de XCas, et je ne tiens pas à passer ma vie là-dessus. Il y a Sage ou Sage Online si on a besoin.
    Par contre si un jour je trouve une librairie C ou C++ (idéalement une header-only) qui s'intègre à R j'essayerai de faire ça.
    Mon package marche très bien pour des petits trucs. C'est bizarre pour Enneper, ce n'est pas un truc énorme non plus. Le code va vite jusqu'à 21 diviseurs puis il est d'une lenteur incroyable. 
  • Tiens, est-ce que vous sauriez s'il est possible de faire une requête HTTP à Sage Online, ou un autre API ?
  • Ah oui, fort possible, il y a ça: https://doc.cocalc.com/api/.
  • Modifié (July 2023)
    Si vous préférez ne pas utiliser C/C++, vous pouvez peut-être rester en local via un appel en javascript à la fonction caseval de la version compilée en JS de giac: https://www-fourier.univ-grenoble-alpes.fr/~parisse/giacwasm.js. Dans du code JS, une fois giacwasm.js chargé, on définit
    var docaseval=Module.cwrap('caseval', 'string', ['string']);
    puis 
    let ans=docaseval("gbasis(...)")

    [Edit] Apparamment, le package V8 de R permet de faire ce genre de choses https://cran.r-project.org/web/packages/V8/




  • Modifié (July 2023)
    Bonjour,

    Oui je connais bien V8. Je préfèrererais en C++, mais je n'ai trouvé que des librairies qui nécessitent une installation pénible. J'ai peut-être mal cherché. Il me faudrait soit une librairie "header-only", ou une librairie compilable directement avec g++ (et qui marche sur Windows notamment, donc pas de dépendance Linux-only). Je vais essayer V8.
  • Modifié (July 2023)
    giac n'a besoin que d'une dépendance obligatoire: une librairie d'entiers en précision arbitraire. Pour les projets libres, c'est GMP qui est utilisé, pour les projets commerciaux closed-source on utilise tommath. giac se compile sous windows, historiquement c'était avec cygwin, maintenant avec mingw : en fait Xcas pour windows est un exécutable de taille modeste avec une grosse DLL giacxcas.dll qui contient tout le moteur de calcul giac et une bonne partie de l'UI. Si vous voulez linker avec giac sous windows, il n'y a donc même pas besoin de compiler giac, il suffit d'utiliser la DLL (sous linux, il suffit d'installer le package dev de giac de votre distribution). Pour visualc++, c'est encore un peu acrobatique, je suis justement en train d'essayer de rendre les choses plus simples.
    Ceci étant dit, le travail pour interfacer avec giac en C++ restera largement plus complexe qu'avec un appel à la version javascript, pour un gain de temps pas très important (un facteur 3 ou plus, selon la taille des calculs de bases de Groebner). 
    Pour illustrer voici un exemple non trivial, le calcul de la base pour cyclic6 en JS:
  • Tiens j'ai raté cette notification. Je ne peux pas inclure une DLL dans un package R si je veux mettre mon package sur CRAN, c'est interdit. Il faut mettre le code C++ source qui est compilé en DLL à l'installation.

    J'ai implémenté la division en C++. En R ça galérait à partir de 21 diviseurs, là ça galère à partir de 24.
  • C'est du JavaScript récent ? Car V8 ne comprend que le vieux JavaScript.
  • Car un JS de 18Mo je n'ose pas l'ouvrir dans un éditeur  :D Surtout avec ce PC. Bon je vais voir si V8 veut bien le sourcer.
  • Hmm ça commence bien: WARNING: using emscripten GL emulation. This is a collection of limited workarounds, do not expect it to work.
  • La ligne var docaseval=Module.cwrap('caseval', 'string', ['string']); est passée sans qu'il bronche. Mais quelle est la commande compléte après ?
  • Modifié (July 2023)
    J'ai fait var ans = docaseval('gbasis([x1^3-2*x1*x2, x1^2*x2-2*x2^2+x1],[x1,x2])') et j'ai obtenu des messages d'erreur :
    Assertion failed: you need to wait for the runtime to be ready (e.g. wait for main() to be called)
    Assertion failed: you need to wait for the runtime to be ready (e.g. wait for main() to be called)
    Error: abort(Assertion failed: you need to wait for the runtime to be ready (e.g. wait for main() to be called)) at Error
        at jsStackTrace (<anonymous>:1:18335100)
        at stackTrace (<anonymous>:1:18335271)
        at abort (<anonymous>:1:18632699)
        at assert (<anonymous>:1:8966)
        at Module.stackSave (<anonymous>:1:18609894)
        at ccall (<anonymous>:1:9817)
        at <anonymous>:1:10152
        at <anonymous>:1:11
    
  • Modifié (July 2023)
    J'ai essayé dans un navigateur mais la page met un temps infini à charger.
    Comment faire avec node ?
  • Modifié (July 2023)
    Ah non c'est le navigateur qui ne marchait pas... J'en ai pris un autre et j'obtiens :
    acwasm.js:1 Uncaught ReferenceError: UI is not defined
        at _emcctime (giacwasm.js:1:18473848)
        at 0345fe1a:0x6dc991
        at 0345fe1a:0x519a1e
        at 0345fe1a:0x2dacc0
        at 0345fe1a:0x3b2905
        at 0345fe1a:0xaf7c46
        at 0345fe1a:0x7b317b
        at 0345fe1a:0x8cbb0
        at 0345fe1a:0x3d089
        at 0345fe1a:0x6f6574
    
  • Le code JS est du code qui contient le code wasm, résultat de la compilation de la librairie giac par emscripten.
    Et en effet désolé, j'ai oublié deux choses importantes: il faut une variable UI javascript qui contient quelques champs
    var UI = {
       Datestart:Date.now(),
       ready:false,
       warnpy:false;
    };

    et il faut que le Module ait eu le temps d'être initialisé avant de pouvoir lancer une commande, ce qui dans un navigateur peut se faire de la façon suivante:
    executer  Module['onRuntimeInitialized'] = function () { console.log('giac is ready'); UI.ready = true; }
    et dans la fonction qui fait l'évaluation caseval, ajout d'un test
    if (!UI.ready)
          window.setTimeout(...); // ou message d'erreur demandant d'attendre l'initialisation

    Avec le module V8 de R, il faudrait savoir comment le code JS d'initialisation du Module fonctionne, et attendre qu'il soit initialisé.




Connectez-vous ou Inscrivez-vous pour répondre.
Success message!