Journées Nationales de Calcul Formel (JNCF) 2013
CIRM, Luminy
13 – 17 mai 2013

JNCF 2013 — Journées Nationales de Calcul Formel
13 – 17 mai 2013

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.
Le volume définitif contenant l'ensemble des supports de cours est désormais disponible sur le site du CEDRAM.

Calcul des invariants d'une action de groupe,

par Evelyne Hubert, INRIA Méditerranée.

Dans ce cours je présenterai le calcul des invariants rationnels des actions de groupes algébriques. J'en détaillerai une application et j'ébaucherai la généralisation aux algèbres d'invariants différentiels.

Dans la première partie je me concentrerai sur le cas relativement simple les dilatations (actions diagonales des tores). Je traiterai le calcul des invariants et la réécriture. L'outil de base est le calcul de la forme de Hermite d'une matrice sur les entiers. Les applications considérées seront:

Dans la deuxième partie je traiterai le cas général des actions rationnelles des groupes algébriques. Les invariants rationnels et la réécriture sont calculés par élimination (base de Gröbner, ensembles triangulaires). J'élaborerai sur la signification géométrique de cette construction. Celle-ci introduit des invariants algébriques, comme le sont les invariants différentiels classiques (longueur d'arc infinitésimale, courbure, torsion).

Optimisation, polynômes, contrôle,

par Didier Henrion, CNRS LAAS, Université de Toulouse.

De nombreux problèmes en contrôle des systèmes se réduisent à la résolution d'équations polynomiales, d'inégalités polynomiales, ou d'équations différentielles polynomiales. Des avancées récentes en optimisation convexe et géométrie algébrique réelle ont pu être combinées pour générer des solutions approchées en arithmétique à virgule flottante.

Dans la première partie du cours, nous décrivons la programmation semi-définie (SDP) comme extension de la programmation linéaire (LP) au cône des matrices semi-définies positives. Nous classifions les fonctions et ensembles semi-définis représentables. Nous insistons sur la dualité entre les problèmes LP sur le cône des mesures non-négatives (et le problème généralisé des moments correspondant) et LP sur le cône des fonctions continues non-négatives (et le problème de la décomposition de polynômes multivariés comme sommes de carrés). Ensuite nous survolons les algorithmes numériques existant pour résoudre les problèmes SDP et les estimations de complexité connues.

Dans la deuxième partie du cours, nous décrivons plusieurs applications récentes de la SDP. Premièrement, nous expliquons comment résoudre des problèmes d'optimisation polynomiale, où un polynôme multivarié réel doit être optimisé sur un ensemble basique semi-algébrique (possiblement non-convexe). Nous insistons sur le calcul d'une solution réelle particulière ou de toutes les solutions réelles d'un système d'équations polynomiales. Deuxièmement, nous étendons ces techniques aux équations différentielles ordinaires (ODE) à dynamique polynomiale ou rationnelle, et le problème de l'optimisation de trajectoire (analyse de stabilité ou de performance de solutions d'ODE). Éventuellement, nous pourrons conclure cette partie sur des applications au contrôle optimal (synthèse d'une trajectoire optimale par rapport à une fonctionnelle donnée).

Pour certains de ces problèmes de décision et d'optimisation, nous espérons que les solutions numériques calculées par la SDP peuvent être raffinées a posteriori et certifiées rigoureusement par des techniques appropriées. Dans ce contexte, nous mentionnons brièvement certains développements récents en calcul numérique/symbolique.

Factorisation des polynômes à  plusieurs variables,

par Grégoire Lecerf, CNRS.

La factorisation irréductible des polynômes à plusieurs variables est connue depuis les années cinquante pour ne pas être calculable pour un corps effectif de coefficients. Néanmoins pour les implémentations habituelles de nombreux corps, dont les nombres rationnels, les nombres algébriques, les corps finis, et les corps de fonctions, nous disposons d'algorithmes de bonne complexité théorique ainsi que d'implémentations performantes dans divers logiciels de calcul formel. Il reste néanmoins plusieurs questions ouvertes importantes puisque dans la plupart des cas on ne connaît pas d'algorithme en temps quasi-linéaire.

Nous commencerons ce cours avec la factorisation séparable, qui permet de scinder un polynôme à une variable en facteurs dont les racines ont la même multiplicité. Nous montrerons comment la factorisation irréductible à une variable se ramène au cas des polynômes séparables. Le cas des polynômes à une variable est en fait critique et nous présenterons les algorithmes désormais classiques lorsque les coefficients sont des nombres rationnels ou appartiennent à un corps fini. Dans un deuxième temps, nous monterons comment ramener la factorisation des polynômes à deux variables à celle à une variable. Enfin, à partir de trois variables, il est souvent favorable de se ramener au cas de deux variables via un théorème dû à Hilbert. L'essentiel du coût de la factorisation devient alors lié à celui des opérations arithmétiques sur les polynômes et séries à plusieurs variables.

Finalement nous mentionnerons brièvement les résultats connus sur la factorisation absolue des polynômes (c'est à dire la factorisation irréductible dans la clôture algébrique du corps des coefficients), et l'application à la décomposition primaire des idéaux d'un anneau de polynômes. Nous finirons avec quelques techniques utiles lorsque les polynômes à factoriser sont composés de très peu de monômes.

Réduction de réseaux et applications

par Damien Stehlé, ENS Lyon.

Un réseau euclidien est l'ensemble des combinaisons linéaires entières des colonnes d'une matrice à coefficients réels. De plus, si ces colonnes sont linéairement indépendantes, on dit qu'elles forment une base du réseau. Pour un réseau donné de dimension >= 2, il existe une infinité de bases possibles. Un problème algorithmique central portant sur les réseaux euclidiens, génériquement appelé réduction de réseaux, consiste ainsi à calculer une base de bonne qualité pour un réseau donné, décrit par une base arbitraire. La ``qualité'' se quantifie à l'aide de l'orthogonalité des vecteurs et/ou de leurs normes.

De nombreux problèmes en informatique et en mathématiques peuvent se ramener à de la réduction de réseaux : factorisation de polynômes à coefficients rationnels, calcul de petites racines de polynômes, calculs dans des corps de nombres, cryptanalyses de nombreux protocoles cryptographiques, approximation de fonctions par des polynômes à petits coefficients, etc.

Ce cours portera sur l'algorithme de réduction de Lenstra, Lenstra et Lovász (LLL). Après une introduction aux réseaux, je présenterai une vision moderne de l'algorithme LLL inspirée de l'algorithme Block-Korkine-Zolotarev (BKZ) de Schnorr et Euchner. Ensuite, je présenterai l'approche actuellement la plus performante pour obtenir des bases réduites au sens de Lenstra, Lenstra et Lovász. Celle-ci mêle des calculs algébriques et numériques, de manière à la fois rigoureuse et efficace. Enfin, si le temps me le permets, je décrirai quelques applications de la réduction de réseaux.

© Clément Pernet 2013.