Introduction au Calcul formel

Présentation

L'objectif principal de cette introduction au calcul formel sera d'en montrer les algorithmes de base, avec, à chaque fois, des exemples d'applications. Les algorithmes étudiés permettrons par exemple de répondre à des questions telles :

• Quelles sont les conformations géométriques possibles en trois dimensions du cyclohexane C₆H₁₂ ?

  (Indication : on sait que les angles entre les liaisons carbone-carbone successives ont pour cosinus -1/3 et que les atomes de carbone sont libres de leur rotation autour des liaisons. On pourra effectuer plusieurs éliminations polynomiales.)

• Quelle est l'enveloppe des cordes d'une ellipse vues sous un angle droit depuis un point donné ?

  (Indication : faire pivoter une paire de droites orthogonales autour du point fixe et obtenir une paramétrisation du point variable.)

• Comment se poursuit la suite (3,0,4,2,3,0,...) d'entiers modulo 5 ?

  (Indication : calculer un approximant de Padé-Hermite.)

• Est-il possible de trouver des entiers e₁, ..., e₅ tels que 12 e₁ + 43 e₂ + 189 e₃ + 19 e₄ + 289 e₅ = 220 ?

  (Indication : utiliser un algorithme de réduction de réseau.)

• L'intégrale de x^1/2(ln x)⁵/(1-x)⁵ de 0 à l'infini est difficilement calculable sous forme explicite ; une évaluation numérique donne la valeur approchée V=-16.6994737192290704961872434007... On a de bonnes raisons de penser que ce nombre s'exprime aisément comme combinaison linéaire des puissances de pi=3.14159... avec des coefficients rationnels. Peut-on trouver s'il y a une telle relation entre V et pi ?

  (Indication : considérer des approximations rationnelles de V et des puissances de pi et utiliser l'algorithme LLL.)

• Dans un modèle simplifié de l'interaction d'une mailloche frappant la membrane d'une timbale circulaire, la détermination des modes propres de la vibration amène à calculer l'intégrale entre -1 et +1 de f_n(p,x)=e^-pxT_n(x)/(1-x²)^1/2. Que vaut cette intégrale ?

  (Indication : écrire un système d'équations différentielles et de récurrences vérifiées par la fonction f_n(p,x) et se débarrasser de x.)

Par les techniques utilisées (souvent, de l'algèbre) et les objectifs visés (algorithmiser des questions mathématiques), le cours s'adresse à un public d'informaticiens mathématiquement réceptifs. Les compléments mathématiques nécessaires, limités, seront faits lorsque le besoin s'en fera sentir.

Déroulement du cours

Contenu du cours

1. entiers, polynômes, séries, algorithme d'Euclide, résultants ;

   Les opérations élémentaires, somme, produit et division d'entiers et de polynômes, sont au centre de la plupart des algorithmes de calcul formel. On présentera quelques solutions classiques pour la multiplication rapide, culminant dans les algorithmes de type FFT (Fast Fourier Transform). On verra ensuite un premier algorithme d'élimination, l'algorithme d'Euclide, qui s'applique aussi bien aux entiers qu'aux polynômes. Ses applications sont nombreuses, on verra notamment les approximants de Padé et les calculs de résultants.

2. algèbre linéaire (produit de matrices, algorithme de Gauss et optimisations) ;

   Les questions relatives aux opérations matricielles sont extrêmement variées. D'une part, on montrera comment la multiplication, l'inversion, le calcul du polynôme caractéristique, sont de complexité équivalente, lorsqu'on traite des matrices à coefficients dans un corps. On introduira la notion d'exposant de l'algèbre linéaire, qui vient mesurer cette complexité. On évoquera ensuite l'algorithmique de l'algèbre linéaire creuse, qui permet de traiter des matrices de taille très conséquente, à plusieurs centaines de milliers d'entrées. Enfin, on traitera des questions relatives aux matrices ayant d'autres types de coefficients, notamment des entrées entières, des séries formelles, voire des nombres flottants.

3. bases de Gröbner et algorithme de Buchberger, résolution de systèmes polynomiaux ;

   Les bases de Gröbner fournissent une extension de l'algorithme d'Euclide pour le cas de polynômes en plusieurs variables. L'algorithme de Buchberger pour le calcul de bases de Gröbner fournit une procédure d'élimination pour le cas de plusieurs variables. Cette approche algorithmique importante a de nombreuses applications en géométrie (notamment en géométrie algébrique), par exemple à la démonstration semi-automatique de théorèmes de géométrie et à la recherche d'équations implicites de courbes algébriques paramétrées. Une autre application très importante est l'utilisation des bases de Gröbner pour la résolution de systèmes de polynômes en plusieurs variables. La contrepartie de la large applicabilité de cette théorie est sa complexité élevée, doublement exponentielle, au moins dans le cas le pire.

4. algorithme de réduction de réseaux (LLL) ;

   Étant donnés des vecteurs V₁, ..., V_m dans l'espace Zⁿ, on appelle réseau engendré par V₁, ..., V_m l'ensemble de leurs combinaisons linéaires à coefficients entiers. Le problème de trouver le plus court vecteur dans un réseau est NP-dur, il est donc peu vraisemblable que l'on dispose prochainement d'un algorithme efficace pour le traiter. Si l'on relâche la contrainte d'optimalité, il devient possible de trouver un vecteur "assez" court en temps polynomial, en utilisant l'algorithme LLL (pour "Lenstra, Lenstra, Lovasz"). Ses applications sont extrêmement nombreuses et vont de la théorie des nombres aux problèmes de sac à dos, en passant par la factorisation des polynômes.

5. intégration symbolique (des fractions rationnelles à l'algorithme de Risch) ;

   À la main, le calcul d'une intégrale définie passe souvent par la recherche d'une primitive. Il en est de même en calcul formel, on l'on recherche de plus une forme explicite. Le cas de base, l'intégration des fractions rationnelles, sera traité en détail, puis l'algorithme de Risch sera abordé dans ses grandes lignes.

6. équations différentielles linéaires (solutions polynomiales, rationnelles, exponentielles, calculs sur leurs solutions).

   Le calcul formel s'intéresse aussi à la résolution en formules explicites d'équations différentielles ou à l'inverse, à la manipulation de solutions données implicitement comme solutions d'équations différentielles. On s'intéressera dans ce cours tout particulièrement au cas des équations différentielles linéaires. On verra tout d'abord comment en rechercher les solutions polynomiales, rationnelles et exponentielles, puis des méthodes de manipulation permettant le calcul d'intégrales définies paramétrées.

Bibliographie

• Handbook of Magma functions (aide en ligne).

• Modern computer algebra (1999). Joachim von zur Gathen et Jürgen Gerhard, Cambridge University Press. [1,2,3,4,5]
• Algorithms for computer algebra (1992). K. O. Geddes, S. R. Czapor et G. Labahn, Kluwer Academic Publishers. [1,2,3,5]
• Algebra and Computation. Notes de cours de M. Sudan. [1,3,4]
• Some tapas of computer algebra (1999). A. M. Cohen, H. Cuypers et H. Sterk, Springer-Verlag (Berlin). [3,4,5]

• Algebraic complexity theory (1997). P. Bürgisser, M. Clausen et M. A. Shokrollahi, Springer-Verlag (Berlin). [1,2]

• Ideals, varieties, and algorithms (1997). D. Cox, J. Little et D. O'Shea, Springer-Verlag (New York), deuxième édition. [3]
• Using algebraic geometry (1998). D. Cox, J. Little et D. O'Shea, Springer-Verlag (New York). [3]
• Gröbner bases and applications (1998). B. Buchberger et F. Winkler, Cambridge University Press. [3]

• Symbolic integration (I) (1997). M. Bronstein, Springer-Verlag (Berlin). [5]

• Cours d'algèbre (1997). M. Demazure, Cassini, Paris. [1]

Exemples de projets envisagés

• Factorisation d'entiers par crible : utilisation de l'algèbre linéaire creuse.
• Bases de Gröbner pour les opérateurs différentiels linéaires.
• L'algorithme de Risch pour l'intégration symbolique indéfinie.