|
|
|
Séminaire
de
Calcul
formel et Complexité
Année
2005-2006
Le séminaire a lieu les vendredis, de 10:30 à 12:00, salle 016, rez-de chaussée du bâtiment 22, Campus de Beaulieu
Octobre 2005
Vendredi 7 octobre
François Boulier (Université de Lille I, LIFL)
Les Bibliothèques Lilloises d'Algèbre Différentielle.
Résumé.
Les BLAD (Bibliothèques Lilloises d'Algèbre Différentielle) sont des bibliothèques logicielles libres (sous licence LGPL) écrites dans le langage de programmation C et dédiées à l'élimination dans les systèmes d'équations différentielles polynomiales. En les réalisant, j'ai voulu obtenir des bibliothèques de calcul symbolique qui puissent facilement être interfacées avec des bibliothèques de calcul numérique dédiées au traitement des équations différentielles. D'un point de vue théorique, ces bibliothèques comportent une définition unifiée des concepts de chaînes régulières algébriques et différentielles [1,2], un algorithme de forme normale d'un polynôme différentiel [3] modulo l'idéal différentiel défini par une chaîne différentielle régulière ainsi que des implantations sophistiquées d'algorithmes tels que Rosenfeld-Gröbner [4] et PARDI [5].
Durant l'exposé, je présenterai les bibliothèques BLAD, la théorie sous-jacente ainsi que deux applications : un problème d'estimation de paramètres dans les systèmes dynamiques [6] et un problème de réduction de modèle appliqué à un modèle d'horloge circadienne [7].
Références :
http://www.lifl.fr/~boulier/BLAD.
Cette page contient en particulier le texte d'un tutoriel assuré lors de l'école d'été « Open Software for Algebraic and Geometric Computation 2005 » organisée en septembre à Sophia Antipolis par Bernard Mourrain et d'autres.
[1] On the theories of triangular sets. Philippe Aubry, Daniel Lazard et Marc Moreno Maza. JSC. 28, 105-124, 1999.
[2] Contribution à l'algorithmique en algèbre différentielle. François Lemaire. Thèse de l'université Lille I. 2002.
[3] Computing canonical representatives of regular differential ideals. François Boulier et François Lemaire. ISSAC 2000.
[4] Representation for the radical of a finitely generated differential ideal. François Boulier, Daniel Lazard, François Ollivier et Michel Petitot. ISSAC 1995.
[5] PARDI ! François Boulier, François Lemaire et Marc Moreno Maza. ISSAC 2001.
[6] System identifiability (symbolic computation) and parameter estimation (numerical computation). Lilianne Denis--Vidal, Ghislaine Joly--Blanchard and Céline Noiret. Math. Comp. in Simulation, 57, 35-44. 2001.
[7] Mechanisms of noise-resistance in genetic oscillators. José Vilar, Hao Yuan Kueh, Naama Barkai et Stanislas Leibler. PNAS 99,9, 5988-5992, 2002.
Vendredi 21 octobre
Annick Valibouze (LIP6, Université Paris VI)
Idéaux de Galois et Groupes (transparents de l'exposé)
Résumé
Savoir si une expression algébrique en les racines d'un polynôme d'une variable est ou non nulle (i.e. est ou non une relation) conduit à étudier l'ensemble des relations entre ces racines. Cet ensemble est un idéal triangulaire dit des relations dont le groupe de décomposition (i.e. celui qui stabilise l'idéal) est le groupe de Galois du polynôme. Cet exposé présentera différents outils et méthodes pour calculer l'idéal des relations et le groupe de Galois. Parmi ces outils, sont les idéaux de Galois.
Novembre 2005
Vendredi 4
Novembre
Sébastien Orange
(LIP6, Université Paris VI)
Calcul du groupe de
décomposition d'un idéal triangulaire - Application
aux idéaux de Galois
Résumé.
Le groupe de
décomposition d'un idéal de k[x_1 , ... , x_n] est
l'ensemble des permutations de x_1 , ...,x_n qui laissent globalement
invariant cet idéal. Ce groupe intervient naturellement en
théorie de Galois effective.
L'algorithme qui sera
présenté effectue le calcul de ce groupe dans le cas d'un
idéal triangulaire. Lorsque cet algorithme est appliqué
aux idéaux de Galois, un résultat nouveau nous permettra
d'interpréter le parcours d'arbre qu'il effectue et
d'évaluer sa complexité. Cet algorithme améliore
deux algorithmes existants de part sa complexité en terme de
tests d'appartenance à l'idéal:
- appliqué aux
idéaux de Galois purs, O(n^2) (la meilleure
compléxité connue étant en O(n^3)) ;
- appliqué aux idéaux de Galois quelconques,
O(n^2 Dim_k (I)^2/(Card(S)*Card(Dec(I))))
où S désigne un
sous groupe de S_n, Dec(I) le groupe de décomposition de I et
Dim_k (I) la dimension de I sur k.
Une comparaison en temps de calcul sera ensuite présentée.
Vendredi
18 Novembre
Ali Ayad
(IRMAR)
Factorisation et
Résolution des polynômes paramétriques.
Du
lundi 21 au vendredi 25 novembre au CIRM (Luminy)
Décembre 2005
Vendredi 2 décembre
Jean-François Mestre (Jussieu)Extensions galoisiennes de groupe de Galois L3(2)
Vendredi 9 décembre, exceptionnellement à 11 heures.
Donald Lutz (Université de San Diego)
On the asymptotic behavior of solutions of linear differential and difference equations.
Abstract.
A fundamental result of N. Levinson concerning the asymptotic integration of linear differential systems has been shown to play a central role in unifying and extending the theory. This theme will be explained and it will be shown how this had lead in recent years to many improvements. Some analogous results in the asymptotic theory of linear difference equations will also be presented.
Janvier 2006
Vendredi
13 janvier
Charlotte Hardouin (Paris 6)
Calcul
du groupe de Galois différentiel d'un produit de trois
opérateurs complètement réductibles.
Vendredi 27 janvier
Martin Celli (Ecole normale supérieure de Pise)La dégénérescence du problème des N corps à somme des masses nulle, une application au calcul des configurations centrales de quatre corps et un cas d'intégrabilité du problème colinéaire des trois corps.
Résumé.
Le problème des N corps consiste en l'étude des équations de Newton, qui décrivent le mouvement d'un système de N particules ponctuelles de masses m1, ..., mN, en interaction gravitationnelle. Pour des masses positives, on sait que ces équations ne sont pas, de différents points de vue, "intégrables" pour N=>3.
Sous l'hypothèse M=m1+...+mN=0, certains calculs deviennent plus simples. Ceci provient du fait que l'intégrale première dépendant du temps m1r1+...+mNrN (r1, ..., rN désignent les positions des corps) ne soit plus un point (le centre d'inertie), mais un vecteur, invariant par translation. Ainsi, sous certaines hypothèses sur les vitesses initiales, le problème colinéaire des trois corps devient intégrable, et l'on est ramené à l'étude du mouvement d'une particule soumise à l'action de trois centres fixes.
L'étude des configurations centrales, qui engendrent les solutions homothétiques du problème des N corps, est une question difficile. A masses positives, leur finitude, qui fait l'objet du sixième problème de Smale pour le 21ème siècle, n'a été établie que pour N<=4 (Hampton-Moeckel, 2004). Pour N=4, on ne sait les dénombrer qu'à masses égales (Albouy, 1996). On établit dans cet exposé certaines propriétés des configurations centrales de quatre corps quand M=0. Par exemple, si le multiplicateur ne s'annule pas, les quatre corps ne sont pas cocycliques. On énumère les configurations centrales de multiplicateur non nul pour les masses x, -x, y, -y.
Les systèmes de N corps de somme des masses nulle apparaissent naturellement dans l'étude des chorégraphies, i.e. des solutions des équations de Newton dans lesquelles les corps se suivent à intervalles de temps égaux sur la même courbe.
Février 2006
Vendredi
17 février
Mickaël Foursov
(IFSIC-IRISA)
Séries formelles et systèmes
dynamiques polynomiaux.
Résumé.
Dans cet exposé nous considérons le problème de
description des séries formelles qui sont des séries
génératrices de systèmes dynamiques affines
polynomiaux. Nous introduisons les notions de grammaires
pondérées de multi-ensembles et des automates
pondérés de multi-ensembles. Nous montrons que les
séries génératrices de systèmes dynamiques
polynomiaux sont engendrées par de telles grammaires. Nous
conjecturons également que toute série formelle
engendrée par une grammaire pondérée de
multi-ensembles est une série génératrice d'un
système dynamique polynomial.
Avril 2006
Vendredi 14 avril, exceptionnellement deux
exposés
-10h30
Jacques-Arthur Weil (LACO, Limoges)
Solutions D-finies de
l'équation de Painlevé VI
-14h00 Ali Ayad
(IRMAR, Rennes)
Complexité de décomposition
des variétés projectives paramétrées
en composantes irréductibles.
Eric Schost (LIX, Ecole Polytechnique)
Changement d'ordre, de la dimension zéro à la dimension positive.
Juin 2006
Attention, les séances du mois de juin ne suivent pas les horaires habituels ...
Mercredi
7 juin, 14 h
Otto Adamou (IRMAR et
Niamey)
Formulations
algébriques des problèmes de base en théorie
du contrôle : quelques exemples.
Lundi 12 juin, 10h30,
salle 006
Frédéric
Besson (IRISA)
Comment
calculer des invariants polynomiaux de programmes ?
Résumé.
Depuis
Tarski [1], il est possible (au moins en théorie) de
vérifier qu'un programme satisfait un invariant polynomial. Pour
ce qui est trouver cet invariant, il existe quelques travaux
récents [2,3,4,5]. Cependant, à l'exception notable de
[5], les méthodes utilisées ne génèrent pas
d'inégalités polynomiales. Pourquoi cet état de
fait ?
N'étant pas un expert du domaine, je compte sur vous pour m'éclairer sur ce point.
Dans cet exposé, je présenterai mon cahier des charges
pour calculer des invariants polynomiaux. Pour cela, je
présenterai l'interprétation abstraite: une
méthode générique pour calculer des invariants de
programmes. Dans ce cadre, un invariant est une solution (la plus
petite possible) d'une contrainte de la forme F(X) <= X où X
est un invariant et F modélise l'effet du programme sur
l'invariant.
J'illustrerai mon propos par des analyses bien connues à base
d'intervalles, octogones, polyèdres convexes. Je conclurai par
un survol des méthodes existantes [2,3,4,5] pour inférer
des invariants polynomiaux.
[1] Tarski, A. A Decision Method for Elementary Algebra and Geometry
[2] Muller-Olm and Seidl. Computing Polynomial Program Invariants. Information Processing Letters. 91(5):233-244, 2004
[3] Rodriguez-Carbonnell E and Kapur, D. Automatic Generation of
Polynomial Loop Invariants: Algebraic Foundations Proc. Intl. Symp on
Symbolic and Algebraic Computation, ISSAC-2004.
[4] Bagnara, Rodriguez-Carbonnell and Zaffanella. Generation of Basic
Semi-algebraic Invariants Using Convex Polyhedra 12th Int. Symposium on
Static Analysis (SAS'05), September 2005, London (UK).
[5] Sankaranarayanan, Sipma, Manna. Non-linear Loop Invariant
Generation using Grobner Bases. in ACM Principles of Programming
Languages (POPL 2004). pp. 318-329
Lundi
19 juin, 14h00, salle 006
Evelyne
Hubert (INRIA Sophia Antipolis, Nice)
Algebraic
Moving Frame: Construction for Local and Algebraic Invariants of
a Group Action.
Résumé.
Group actions are ubiquitous in mathematics and arise in diverse fields
of science and engineering. Their invariants provide elegant solutions
to classification and equivalence problems. From a computational point
of view they are used to take into account the symmetry of a problem.
I shall present anew the construction of local invariants of a Lie
group action by the so called "moving frame" method. Originally due to
Cartan and it was revisited by Fels & Olver more recently. New
algebraic foundations provide a computational alternative to this
construction.
Besides, when considering a rational group action, I show an algorithm
to compute a generating set of rational invariants. The output of the
algorithm also provides a simple algorithm to rewrite any rational
invariant in terms of those generators.
The talk is based on joint workwith Irina Kogan, North Carolina State University.
Mardi
20 juin, 10h30
Colas Bardavid (IRMAR)
A
propos de la méthode de Mitschi-Singer pour le problème
inverse en théorie de Galois différentielle.
---------------------------------------------------
Responsable du séminaire : D. Boucher