Algorithms Project's Seminar

The project Algorithms of INRIA runs a seminar devoted to the analysis of algorithms and related topics. The subjects covered include combinatorics, symbolic computation, asymptotic analysis, average-case analysis of algorithms and data structures, and computational number theory.

The talks are held in the conference room of Building 9 at INRIA-Rocquencourt, near Paris. Contact information is given below, and directions on how to get to Rocquencourt are available here (in French).

Upcoming Talks in the Year 2011–2012

• 10h30: Pierre Charollois, Institut Mathématique de Jussieu.

  Calcul efficace des sommes de Dedekind-Sczech.

  On détaillera la méthode de Gunnells-Sczech pour obtenir la valeur exacte de la série double

  ∑ m, n

  1  (21052012  m   +   67354 n)2 · (1789286  m + 438935 n)3

  ,

  et de familles de séries similaires en dimension r. La méthode met en jeu l’algorithme LLL et une relation de cocycle pour GL_r−1(ℚ).

• 14h00: Alain Lascoux, Université de Marne-la-Vallée.

  Représentations du groupe symétrique, Pfaffiens et déterminants.

  Un Pfaffien en les (a_i−a_j)/(x_i+x_j) peut se calculer en faisant appel au groupe symétrique agissant sur les a_i et à celui agissant sur les x_j. Cette interprétation s’adapte facilement à des Pfaffiens et des déterminants de fonctions beaucoup plus générales, par exemple des déterminants et des Pfaffiens de mineurs. On se ramène ainsi à la combinatoire des représentations, où apparaissent en particulier graphes de Yang-Baxter et chemins de Dyck.

• 11h00: Steve Melczer, visiting from SFU, Canada and Microsoft Research - Inria Joint Centre

  Attention, l'exposé aura lieu au bâtiment I, au 1er étage du Parc Orsay Université.

  Lattice Walks Restricted to the Positive Quarter Plane (and Octant).

  The enumeration of lattice walks in restricted regions is an elegant problem which has recently been the subject of much attention. In this talk, we begin by reviewing previous work on classifying the generating functions of walks with unit steps restricted to the positive quarter plane. The use of 'guess-and-check' methods for determining asymptotics of these walks will also be discussed, followed by the current progress on walks restricted to the positive octant. These new results in three dimensions are obtained by methods which are analogous to those used previously in two dimensions, as well as combinatorial reductions between two and three dimensional walks.

• 10h30: Jean-Claude Yakoubsohn, Institut Mathématique de Toulouse.

  Calcul des racines multiples.

  Il est bien connu que la méthode de Newton ne converge pas quadratiquement au voisinage d'une racine multiple. Le but de cet exposé est d'expliquer comment retrouver cette convergence quadratique.

• 14h00: Jacques Sauloy, Institut Mathématique de Toulouse.

  L'analogue du phénomène de Stokes pour les équations aux q-différences.

  Dans la dernière décennie, nous (= Ramis, Sauloy, Zhang) avons défini un phénomène de Stokes pour les équations aux q-différences linéaires analytiques complexes. Nous l'avons appliqué à la classification analytique locale et à la théorie de Galois locale. Je décrirai ce phénomène en le comparant au phénomène de Stokes "classique" des équations différentielles et je résumerai les principaux résultats obtenus et les problèmes en suspens.

This Year's Past Talks (2012)

• 10h30: Assia Mahboubi, Marelle, INRIA Saclay.

  Calcul et calcul formel dans un assistant à la preuve.

  Une des spécificités du système Coq est la place que la notion de calcul occupe dans le formalisme logique sous-jacent à cet assistant à la preuve. Une conséquence en est que l'on dispose dans ce système d'un véritable langage de programmation fonctionnel, qui peut être utilisé pour modéliser mais aussi pour exécuter (relativement efficacement) des programmes, garantissant ainsi la correction des valeurs calculées. Cette utilisation du calcul, combinée avec le développement récent d'un nombre substantiel de bibliothèques de mathématiques formalisées, est particulièrement propice à l'implémentation et à la certification en Coq d'algorithmes issus du calcul formel. Dans cet exposé, après une brève introduction au système, et aux techniques pour exploiter cette place du calcul dans les preuves formelles, nous proposerons un tour (nécessairement non exhaustif) de quelques expériences en cours autour du mariage entre preuves formelles et calcul formel. Cet exposé ne présuppose aucune connaissance de Coq ou de culture en théorie des types.

• 14h00: Pierre Lairez, Algorithms, INRIA Paris-Rocquencourt.

  Résolution algorithmique des singularités.

  Après avoir expliqué les tenants et les aboutissants de la désingularisation, on présentera l'algorithme de E. Bierstone et P. Milman pour résoudre les singularités d'une variété en caractéristique nulle. On détaillera particulièrement le principe de la récurrence sur la dimension (contact maximal) et l'importance de la fonctorialité, grande force de la méthode. J'essaierai de proposer un exposé pratique et calculatoire, loin des sphères planantes de la géométrie algébrique.

• 10h30: Delphine Boucher, Université de Rennes 1.

  Codes linéaires à base de polynômes tordus avec automorphismes et dérivations.

  Partant des codes θ-cycliques définis sur un corps fini F, où θ est un automorphisme de F, on introduit la notion de (θ, δ)-codes modules et la notion de (θ, δ)-codes d'évaluation, où δ est une θ-dérivation sur F. Dans cet exposé, on cherchera à établir des liens (égalité, équivalence, dualité) entre ces codes et à construire des sous-familles présentant des propriétés particulières (par exemple de décodage). C'est un travail en commun avec Felix Ulmer.

• 14h00: Jérémy Berthomieu, Université de Versailles.

  Algorithmes détendus rapides pour la remontée de Hensel p-adique et applications aux systèmes algébriques.

  Après avoir rappelé ce qu'est une représentation paresseuse des séries formelles ou des entiers p-adiques, j'expliquerai la multiplication détendue, introduite initialement par Fischer et Stockmeyer pour les entiers, et par van der Hoeven pour les polynômes et séries formelles, et dont la complexité est quasi-linéaire en la précision. Je présenterai ensuite nos algorithmes pour résoudre un polynôme à une variable, un système linéaire et enfin un système algébrique sur les entiers p-adiques, avec une complexité encore quasi-optimale en la précision. Des exemples de notre implantation en C++ pour Mathemagix et une comparaison avec Linbox seront donnés. Il s'agit d'un travail en collaboration avec Romain Lebreton.

• 10h30: Thomas Cluzeau, Université de Limoges.

  Computing Closed Form Solutions of Integrable Connections.

  In this talk, I will present algorithms for computing rational and hyperexponential solutions of linear D-finite partial differential systems written as integrable connections. In particular, I will show that these types of solutions can be computed recursively by adapting existing algorithms handling ordinary linear differential systems. The arithmetic complexity of the algorithms will be discussed. Finally, I will illustrate the result of a Maple implementation (available at http://www.ensil.unilim.fr/~cluzeau/PDS.html) on some examples.

• 14h00: Joris van der Hoeven, LIX, École polytechnique.

  On the complexity of skew arithmetic.

  Let K be an effective field of constants of characteristic zero, so that all field operations can be carried out by algorithms. Given an indeterminate x and the derivation delta = x d / d x, we will study various operations in the skew ring K[x, delta], such as multiplication, division, greatest common divisors, series solutions, etc. In analogy with the commutative case, we will give bounds for the computational complexities of these operations in terms of the complexity of operator multiplication.

• 10h30: Gilles Christol, Institut Mathématique de Jussieu.

  Diagonales de fractions rationnelles et équations différentielles auto-adjointes.

  Le but de l'exposé est d'expliquer comment la dualité de Poincaré permet de relier la diagonale d'une fraction rationnelle à plein d'équations différentielles auto-adjointes. La démonstration repose sur des théories abstraites (D-modules, structures de Hodge) mais dont les résultats ont des traductions très concrètes sinon toujours calculables.

This Year's Past Talks (2011–2012)

• Symbolic Integration in Differential Fields, by Clemens Raab (November 28, 2011). Abstract. Slides.
• Marches dans un quart de plan : quelques avancées récentes, by Kilian Raschel (November 28, 2011). Abstract.
• Critères pour l'intégralité des coefficients de, by Éric Delaygue (November 07, 2011). Abstract. Slides.
• Lattice Green's Functions of the Higher-Dimensional Face-Centered Cubic Lattices, by Christoph Koutschan (November 07, 2011). Abstract. Slides.
• Réduction de Moser des réseaux à connexion, by Eduardo Corel (October 24, 2011). Abstract. Slides.
• Méthodes algébriques pour la résolution, by Carole El Bacha (October 24, 2011). Abstract. Slides.
• Sur le nombre d'intervalles dans les treillis de Tamari, by Éric Fusy (October 03, 2011). Abstract. Slides.
• Cayley-type identities: new combinatorial proofs and applications to non-perturbative quantum field theories, by Andrea Sportiello (October 03, 2011). Abstract.
• Mean asymptotic behaviour of radix-rational sequences and dilation equations, by Philippe Dumas (September 05, 2011). Abstract. Slides.
• Regular Sequences, by Eric Rowland (September 05, 2011). Abstract. Slides.

Talks from Previous Years

Until 2005, we published yearly Seminar Proceedings that contain summaries of the talks. The proceedings for the years 1991-2005 can be accessed here. The proceedings for all years can also be accessed here.

   Contact Information