00:00:00 / 00:00:00

Du calcul des racines réelles de polynômes à celui de la topologie de courbes algébriques planes. (1/6)

By Marie-Françoise Roy

Appears in collection : Du calcul des racines réelles de polynômes à celui de la topologie de courbes algébriques planes

D'un point de vue historique, il semble approprié d'appeler la recherche des racines d'un polynômes le Problème Fondamental de l'Algèbre Effective. Elle a occupé les mathématiciens de façon continue dès les premiers jours, et a été jusqu'au XIXe siècle l'une de leurs préoccupations majeures. Descartes, Newton, Hermite et Sylvestre ont écrit sur ce sujet. Cet intérêt a toujours été de nature intensément algorithmique, ce qui crée un lien direct avec l'informatique moderne et la complexité des algorithmes.

Il existe deux axes distincts d'investigation du Problème Fondamental de l'Algèbre Effective. La première est l'approche algébrique avec comme exemple le plus remarquable la méthode astucieuse de Sturm, tandis que l'approximation numérique des racines représente l'autre approche aboutissant à la méthode bien connue de Newton. Des traitements modernes du problème peuvent être trouvés dans [1], que nous utiliserons comme référence de base pour le cours, mais il existe des résultats récents, non inclus dans [1] que nous discuterons également.

En particulier, étant donné un polynôme univarié de degré $d$ à coefficients entiers de taille binaire bornée par $\tau$, des travaux récents dans [2], montrent comment isoler donc approximer toutes les racines réelles d'un polynôme, à toute précision prescrite $\rho\gt 0$, en temps $\tilde{O}(d^2\tau+d^3+d\rho)$.

Il s'avère que le comptage et la localisation des racines réelles d'un polynôme univarié réel est la pierre angulaire de la plupart des algorithmes calculant la topologie des courbes algébriques réelles planes. En effet isoler les racines réelles du discriminant de la courbe algébrique (correspondant à la projection des points singuliers et critiques de la courbe sur l'axe des abscisses) est incontournable pour toutes les méthodes basées sur l'approche Décomposition Cylindrique Algébrique. Nous terminerons ce cours en décrivant un algorithme récent [3] qui calcule la topologie d'une courbe algébrique plane définie comme l'ensemble des zéros d'un polynôme bivarié de degré $d$ et à coefficients entiers de taille binaire bornée par $\tau$ dans $\tilde{O}(d^5\tau+d^6)$ opérations binaires.

Information about the video

Bibliography

  • [1] Saugata Basu, Richard Pollack, and Marie-Fran coise Roy. Algorithms in real algebraic geometry, volume 10. Berlin: Springer, 2006.
  • [2] Kurt Mehlhorn, Michael Sagraloff, and Pengming Wang. From approximate factorization to root isolation with application to cylindrical algebraic decomposition. Journal of Symbolic Computation, 66:34-69, 2015.
  • [3] Daouda Niang Diatta Seny Diatta Michael Sagraloff Marie-Francoise Roy and Fabrice Rouiller. Bounds for polynomials on algebraic numbers and application to curve topology. Accepted for publication to the Journal of Discrete and Computational Geometry, 2022.

Last related questions on MathOverflow

You have to connect your Carmin.tv account with mathoverflow to add question

Ask a question on MathOverflow




Register

  • Bookmark videos
  • Add videos to see later &
    keep your browsing history
  • Comment with the scientific
    community
  • Get notification updates
    for your favorite subjects
Give feedback