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

JNCF 2014 — Journées Nationales de Calcul Formel
3 – 7 Novembre 2014

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.

Structured matrices and applications,

par Dario Andrea Bini, département de Mathématiques de l'Université de Pise.

In this short course, we examine the main properties of two wide classes of structured matrices: Toeplitz-like matrices, and quasi-separable matrices. While the former class has a close interplay with polynomials, Laurent polynomials, and Laurent power series, the latter class is somehow related to the problem of computing the roots of a matrix polynomial.

We show some applications of Toeplitz matrices and quasi-separable matrices. In particular we describe, a recent application in the field of stochastic processes where one has to compute the exponential function of a block triangular Toeplitz matrix. Moreover, we show how a matrix polynomial can be linearized by means of quasiseparable companion-like matrix pencils and how this structure can be exploited in the design of algorithms for the polynomial eigenvalue problem.

Factorisation d'entiers et problèmes du logarithme discret,

par Pierrick Gaudry, CNRS.

Calculer la factorisation d'un entier est un problème célèbre pour sa difficulté qui remonte à l'antiquité ; les applications en cryptographie sont bien connues. Le problème du logarithme dans les corps finis est plus récent (disons, qu'il est centenaire), et est d'un intérêt cryptographique comparable. Depuis les années 80, il est aussi courant de s'intéresser à la variante du logarithme discret qui s'exprime dans une courbe elliptique.

L'objectif du cours est d'offrir une visite guidée de quelques algorithmes liés à ces questions, en insistant sur les liens avec le calcul formel.

Dans un premier temps, nous présenterons ces problèmes, en les replaçant dans leur contexte cryptographique. Nous poursuivrons avec une étude d'un principe algorithmique général : la combinaison de congruences de «petits» éléments. Ce principe sera instancié dans une version élémentaire pour tous les problèmes considérés, puis nous proposerons deux zooms sur des algorithmes plus avancés.

Le premier zoom concerne le problème du logarithme discret dans les corps finis de petite caractéristique, pour lequel un algorithme de complexité quasi-polynomiale a récemment été découvert. En pratique, les calculs pour cette classe de problèmes impliquent de nombreuses résolutions de systèmes polynomiaux bi-homogènes d'une forme bien particulière.

Le second zoom concerne le problème du logarithme discret dans les corps premiers par l'algorithme du crible algébrique. Un des points dominants du calcul est la détermination du noyau d'une grosse matrice creuse définie sur un assez gros corps fini.

Ces deux exemples illustrent que pour ce type de travaux, il est nécessaire d'aller au-delà d'une utilisation «en boîte noire» des méthodes de calcul formel : prendre en compte les particularités des problèmes permet alors de gagner en efficacité.

Overview of communication avoiding algorithms in linear algebra and beyond,

par Laura Grigori, INRIA Paris - Rocquencourt.

The cost of moving data in an algorithm can surpass by several orders of magnitude the cost of performing arithmetics, and this gap has been steadily and exponentially growing over time. In this short course I will explain that this communication problem needs to be addressed directly at the mathematical formulation and the algorithmic design level. This requires a paradigm shift in the way the numerical algorithms are devised, which now need to aim at keeping the number of communication instances to a minimum, while retaining their numerical efficiency.

Communication avoiding algorithms provide such a novel perspective on designing algorithms that provably minimize communication in numerical linear algebra. The novel numerical schemes employed, the speedups obtained with respect to conventional algorithms, as well as their impact on applications in computational science will be also discussed. Connections with the computer algebra community will be discussed as well.

Algèbre constructive,

par Henri Lombardi, département de Mathématiques de l'Université de Franche-Comté.

Dans ce tutoriel, on va essayer de convaincre l'auditoire que l'Algèbre abstraite contemporaine est pour l'essentiel constructive si l'on prend la peine de « bien lire » les démonstrations usuelles.

Lorsque l'on veut examiner le contenu concret d'un théorème d'algèbre et que l'on regarde sa démonstration en détail, si celle-ci ne se laisse pas traduire en un algorithme, on se heurte usuellement à deux obstacles :

Par exemple, le Moderne Algebra de van der Waerden évite le deuxième obstacle en ne considérant que des structures algébriques dénombrables.

Mais le lemme de Zorn revient la plupart du temps à agiter les mains dans le vide pour détourner l'attention du véritable problème, lequel se trouve aux étages finis de la construction, et non dans le passage à la limite. Si ce dernier n'est pas vraiment possible, cela n'affecte en rien le contenu concret du théorème. En Calcul Formel, on ne passe jamais à la limite, car on s'intéresse au contenu concret des théorèmes, en outre les ordinateurs ne peuvent pas « passer à la limite » en un temps fini.

La pratique montre que le principal obstacle pour mettre à jour la véritable signification d'un théorème, provient de l'utilisation du principe du tiers exclu.
Or le moyen de contourner l'obstacle du tiers exclu est une pratique courante en Calcul Formel, sous le nom de l'évaluation paresseuse. Le paradigme est fourni par la méthode D5 qui permet de calculer dans la clôture algébrique d'un corps explicite, sans jamais se tromper, même si aucune clôture algébrique de ce corps ne peut être construite (au sens usuel de la chose). L'existence d'un diviseur irréductible pour un polynôme donné de K[X] (K un corps explicite), laquelle se prouve en maths classiques au moyen du principe du tiers exclu, y est remplacée par un calcul paresseux arborescent et sans erreur possible.

Le plan des exposés est le suivant.
Dans chaque section on montre comment se débrouiller constructivement avec des notions et des théorèmes d'apparence non constructive (au premier abord).

  1. Théorème de la base adaptée. Noethérianité constructive.
  2. Nullstellensatz sans clôture algébrique.
  3. Dimension de Krull.
  4. Idéaux premiers minimaux et maximaux.

Références.
Livres

Articles

© Adrien Poteaux 2014.