Journées Nationales de Calcul Formel 2017
CIRM, Luminy, 16–20 janvier 2017

Journées Nationales de Calcul Formel — 16–20 janvier 2017

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.

Suite à un empêchement de l'orateur, le cours de Moulay Barkatou Algorithmes pour la résolution de systèmes d’équations différentielles linéaires à coefficients polynomiaux initialement annoncé est remplacé par un cours d'Alin Bostan intitulé Computer Algebra for Lattice Path Combinatorics.

Dynamique symbolique et représentations

par Valérie Berthé (CNRS, LIAFA, Université Paris 7)

Un système dynamique discret est la donnée d'une transformation continue agissant sur un espace compact. Le qualificatif discret renvoie au temps qui est discrétisé : au temps n, on considère la n-ième itération de cette transformation. En se fixant une partition, on peut coder à l'aide de suites de symboles les trajectoires du système dynamique, selon les éléments de cette partition. On obtient ainsi un système dynamique symbolique, constitué d'un ensemble de suites de symboles sur lequel le décalage agit (le décalage consiste à supprimer le premier terme d'une suite). Ces codages symboliques, si la partition est bien choisie, permettent l'analyse statistique (via la théorie ergodique) des systèmes dynamiques sous-jacents. Nous considérerons ici, en particulier, des systèmes dynamiques de nature arithmétique qui permettent la représentation et la manipulation symbolique des nombres (ou de séries formelles), comme la beta-numération ou les fractions continues. Nous allons de plus nous intéresser aux orbites qui apparaissent naturellement en informatique, à savoir, les orbites périodiques et finies.

Notes | Support

Computer Algebra for Lattice Path Combinatorics

par Alin Bostan (Inria Saclay Île-de-France)

Classifying lattice walks in restricted lattices is an important problem in enumerative combinatorics. Recently, computer algebra has been used to explore and solve a number of difficult questions related to lattice walks. In this series of talks, we will give an overview of recent results on structural properties and explicit formulas for generating functions of walks in the quarter plane, with an emphasis on the algorithmic methodology.

Résumé détaillé | Support 1, 2, 3 | Référence

Condition: The Geometry of Numerical Algorithms

par Peter Bürgisser (Institut für Mathematik, Technische Universität Berlin)

The performance of numerical algorithms, both regarding stability and complexity, can be understood in a unified way in terms of condition numbers. This requires to identify the appropriate geometric settings and to characterize condition in geometric ways.

A probabilistic analysis of numerical algorithms can be reduced to a corresponding analysis of condition numbers, which leads to fascinating problems of geometric probability and integral geometry. The most well known example is Smale's 17th problem, which asks to find a solution of a given system of n complex homogeneous polynomial equations in n+1 unknowns. This problem can be solved in average (and even smoothed) polynomial time.

In the course we will explain the concepts necessary to state and solve Smale's 17th problem. We also show how these ideas lead to new numerical algorithms for computing eigenpairs of matrices that provably run in average polynomial time. Making these algorithms more efficient or adapting them to structured settings are challenging and rewarding research problems. We intend to address some of these issues at the end of the course.

More information on the subject can be found in the recent monograph Condition with Felipe Cucker, see http://www.springer.com/us/book/9783642388958.

Support | Vidéo

Algorithmique des nombres p-adiques

par Xavier Caruso (CNRS, Institut de recherche mathématique de Rennes, Université Rennes 1)

Les nombres p-adiques ont été introduits à la fin du 19ème par Kurt Hensel. Ils ont acquis une notoriété et une importance grandissante tout au long du 20ème siècle au point d'être devenu aujourd'hui un outil essentiel dans de nombreuses branches de la théorie des nombres et de la géométrie arithmétique.

Les nombres p-adiques ont également trouvé leur place dans le domaine du calcul formel puisqu'ils interviennent de manière cruciale dans plusieurs algorithmes classiques, les plus célèbres d'entre d'eux étant probablement les algorithmes de comptage de points à la Kedlaya. Néanmoins, à l'instar des nombres réels, les nombres p-adiques ne peuvent être représentés que de manière approchée sur machine. Ceci rend leur manipulation algorithmique délicate et conduit à des questions sur la gestion de la précision analogues à celles qui se posent en arithmétique des ordinateurs.

Après une longue introduction de présentation des nombres p-adiques et de la manière dont ils interviennent en calcul formel, ce cours se fixera pour objectif, d'une part, d'expliquer les principaux paradigmes en vigueur pour la manipulation des nombres p-adiques sur ordinateur et, d'autre part, de donner les outils pour permettre une étude fine de la stabilité numérique des algorithmes faisant intervenir des p-adiques. De nombreux exemples concrets issus de l'algèbre linéaire ou de l'algèbre commutative viendront illustrer notre propos.

Plan (indicatif) :

Notes | Support