Journées Nationales de Calcul Formel (JNCF) 2010
CIRM, Luminy
3 – 7 mai 2010

JNCF 2010 — Journées Nationales de Calcul Formel
3 – 7 mai 2010

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.

Daniel Augot, Décodage des codes géométriques et algorithmes de Guruswami-Sudan

Le premier exposé reprend les algorithmes classiques de décodage des codes géométriques, basés sur l'algorithme de Berlekamp-Massey et ses généralisations multivariées (Berlekamp-Massey-Sakata). Toutefois, avant de présenter ces algorithmes, je rappelerai les bases de la théorie des codes : codes linéaires, borne de Singleton, codes de Reed-Solomon, borne de Hamming. Ensuite, j'introduirai de manière motivée la famille des codes géométriques, comme généralisation des codes de Reed-Solomon, après un bref rappel de la théorie des courbes algébriques sur les corps finis. La cadre sera alors en place pour introduire le décodage par syndrômes, qui est le décodage classique des codes géométriques.

Le deuxième exposé est consacré aux progrès récents dans le domaine du codage algébrique, qui reposent sur le décodage par interpolation. Ces progrès sont dus à Guruswami-Sudan, et reposent sur une vision duale des codes de Reed-Solomon et des codes géométriques. Je présenterai dans l'ordre les algorithmes de Berlekamp-Welsh, Sudan et Guruswami-Sudan, dans le contexte des codes de Reed-Solomon et dans le contexte des codes géométriques. On verra finalement comment l'algorithme de Berlekamp-Massey-Sakata peut être recyclé dans ce contexte.

Alin Bostan, Algorithmes rapides pour les polynômes et matrices

Les principaux thèmes de cet exposé sont la conception et l'analyse d'algorithmes pour deux types spécifiques de calculs algébriques: avec des polynômes et des séries formelles à une variable, d'une part, et avec des matrices denses et des matrices structurées, d'autre part. De nombreuses applications seront décrites, concernant la manipulation rapide des fonctions rationnelles, des matrices polynomiales, des nombres algébriques, des fonctions algébriques, des récurrences et des opérateurs différentiels.

L'accent sera mis principalement sur la complexité asymptotique, et sur l'illustration des paradigmes fondamentaux (diviser-pour-régner, pas de bébé/pas de géant, principe de transposition) et des techniques (exponentiation binaire, itération de Newton, évaluation-interpolation), utilisées dans la conception et l'analyse des algorithmes.

Dans la première partie de l'exposé, nous montrerons comment, en utilisant de telles techniques, une multitude d'opérations sur les polynômes et les séries (division, logarithme, exponentielle, évaluation, interpolation, changement de base, composition, plus grand commun diviseur, résultant, approximants de Padé et de Padé-Hermite,...) peuvent être ramenées ultimement à la multiplication polynomiale, et héritent ainsi de sa bonne complexité.

Dans la deuxième partie de l'exposé, nous examinerons d'abord la complexité des calculs avec les matrices denses (inversion, décomposition LU, calcul du déterminant et du polynôme caractéristique,...), en les ramenant à la multiplication de matrices. Puis, nous présenterons un traitement unifié des calculs avec les matrices structurées (Toeplitz, Hankel, Vandermonde, Cauchy, Sylvester, et leurs généralisations), montrerons leurs liens avec les calculs polynomiaux, et exploiterons ces corrélations pour obtenir des accélérations significatives par rapport au cas des matrices denses.

Une liste de problèmes ouverts conclura l'exposé.

Jean-Pierre Dedieu, Complexité et conditionnement

Peut-on facilement calculer, de façon approchée, un zéro d'un système de n équations polynomiales en n inconnues à coefficients complexes ? Quelle est la complexité d'un tel calcul ? L'approche que nous présentons au cours de ces exposés utilise un modèle de calcul sur les nombres réels et privilégie les méthodes homotopiques. Nous verrons comment relier la complexité d'un tel calcul au conditionnement des systèmes rencontrés lors du parcours homotopique et nous montrerons comment rechercher des trajectoires optimales.

Alban Quadrat, Une introduction à l'analyse algébrique constructive et à ses applications

Le but de ce mini-cours est de présenter une introduction à l'analyse algébrique constructive et à certaines de ses applications récentes en théorie des systèmes, théorie du contrôle et physique mathématique.

L'analyse algébrique est une branche récente des mathématiques qui étudie les systèmes linéaires d'équations aux dérivées partielles à l'aide de techniques venant de la théorie des modules, de l'algèbre homologique et de la théorie des faisceaux. Elle a été développée dans les annnées soixante par Malgrange, Palamodov, Bernstein, Sato, Kashiwara... Certaines des idées et techniques développées pour les systèmes différentiels se généralisent à d'autres classes de systèmes linéaires fonctionnels telles que les systèmes d'équations aux différences, systèmes d'équations différentiels à retards...

Nous montrons comment les techniques de l'algèbre constructive (e.g., bases de Gröbner ou Janet pour des anneaux d'opérateurs non-commutatifs tels que des algèbres de Ore) permettent de développer une approche constructive de la théorie des modules et de l'algèbre homologique. Nous interpréterons alors certaines propriétés des modules dans le langage des systèmes et nous montrerons comment des problèmes classiques en théorie des systèmes (e.g., existence de paramétrisations, équivalences, symétries, factorisations, réductions, décompositions, lois de conservation) trouvent alors des réponses simples et constructives.

Nous illustrerons ces nouvelles techniques à l'aide de nombreux systèmes classiques venant de la physique mathématique et de la théorie du contrôle à l'aide des packages OreModules, OreMorphisms, QuillenSuslin, Stafford, Serre et Homalg.


© Grégoire Lecerf, 2010.