Journées Nationales de Calcul Formel (JNCF) 2015
Cluny
2 – 6 Novembre 2015
JNCF 2015 — Journées Nationales de Calcul Formel
2 – 6 Novembre 2015
Cours
Quatre cours de trois heures sont prévus. Le reste du temps sera consacré à des exposés d'une vingtaine de minutes portant sur des travaux de recherche récents, principalement proposés par des doctorants et post-doctorants.De la décomposition aux intégrales premières rationnelles
par Guillaume Chèze, Institut de Mathématiques de Toulouse.
Dans ce cours nous commencerons par étudier le problème de décomposition suivant:
Soit f, h ∈
K(X,Y) et
u ∈ K(T) tels
que f=u(h)
et deg(u)≥ 2.
Peut on calculer à partir de f les fractions
rationnelles u et h ?
Nous verrons alors que ce problème est un problème de factorisation particulier
et que nous pouvons construire des algorithmes efficaces pour le résoudre. Ensuite,
afin d’améliorer la compréhension du problème et certains algorithmes
obtenus, nous serons amenés à considérer le problème plus large du calcul
des intégrales premières rationnelles d’un champ de vecteurs polynomial du plan.
Nous présenterons alors des résultats théoriques liés à ce problème:
théorème de Darboux, et de Jouanolou, mais aussi des algorithmes et des problèmes ouverts.
Résolution de systèmes polynomiaux avec les bases de Gröbner.
par Jean-Charles Faugère, INRIA Paris - Rocquencourt.Le problème abordé dans ce cours est le problème fondamental de la résolution d'équations polynomiales par des méthodes de Calcul Formel. Il existe de nombreuses méthodes exactes permettant de résoudre ces systèmes (résultants, ensemble triangulaires, bases de bord, etc) ou semi-numériques (homotopies). Nous nous restreignons ici au calcul des bases de Gröbner.
Géométrie tropicale appliquée à la programmation linéaire, aux jeux avec paiement moyen et aux problèmes de valeurs propres.
par Stéphane Gaubert, INRIA Saclay.Dans ce cours, nous présenterons des applications récentes de la géométrie tropicale à des problèmes qui relèvent de l’optimisation, de la théorie des jeux, ou du calcul numérique de valeur propre. En chemin, nous ferons un tour d’horizon introductif de quelques méthodes du domaine. De manière schématique, le point de vue tropical consiste à raisonner combinatoirement sur les images par une valuation d’objets classiques. La valuation peut être non-archimédienne, comme l’exposant d’une série de Puiseux, ou bien archimédienne, comme le log du module d’un nombre complexe. On met en particulier en évidence un lien entre des problèmes d’algèbre linéaire et certains problèmes polynomiaux, d’une part, et des problèmes de jeux avec paiement moyen, d’autre part. De la sorte, les programmes linéaires tropicaux, ou les jeux avec paiement moyen, se relèvent en des programmes linéaires classiques sur des corps ordonnés munis de valuations non-archimédiennes ou bien en des programmes linéaires avec de grands coefficients réels. Ceci a permis de relier deux questions ouvertes: - l’existence d’un algorithme polynomial pour les jeux avec paiement moyen (l’un des problèmes “classiques” dans NP ∩ coNP qui n’est pas connu être dans P) - l’existence d’une règle de pivotage fortement polynomiale en programmation linéaire (l’existence d’un algorithme fortement polynomial en programmation linéaire est un autre problème connu, posé par Smale). Une réponse positive à la seconde question impliquerait une réponse positive à la première. La même approche conduit à des exemples pathologiques de programmes linéaires dans lesquels le chemin central (la courbe algébrique qui est l’outil fondamental des méthodes de points intérieurs) a une grande courbure totale, un phénomène inattendu en programmation linéaire. Une dernière application concerne les bornes de nature tropicale sur les valeur propres. Celles-ci permettent de contrôler les ordres de grandeur des valeurs propres à partir des ordres de grandeur des coefficients, ce qui peut être exploité dans des algorithmes numériques.
Ce cours s’appuie sur des travaux avec différents coauteurs: M. Akian, X. Allamigeon, R. Bapat, P. Benchimol, A. Guterman, M. Joswig, A. Marchesini et M. Sharify.
Algorithms for D-finite Functions
par Manuel Kauers, Johannes Kepler University, Linz, Autriche.D-finite functions play an important role in the part of computer algebra concerned with algorithms for special functions. They are interesting both from a computational perspective as well as from the perspective of applications. We give an overview over the main properties and the classical algorithms for D-finite functions.