Vendredi 17
Septembre
2004 , 10h30
Philippe Gaillard (IRMAR)
Applications de la
théorie de Galois différentielle aux
équations différentielles linéaires d'ordre 4
Résumé (voir aussi
fichier .ps)
Pour les équations différentielles linéaires
d'ordre 2 et 3, des algorithmes de résolution exacte avec
des temps de calcul réalistes existent, se fondant sur une
étude préalable précise des groupes
apparaissant comme groupes de Galois différentiels de ces
équations. Plusieurs études de l'ordre 4 ont
déjà eu lieu mais
ne concernaient qu'un aspect particulier de la classification des
groupes. Dans cet exposé,
on rappelle les bornes optimales pour le degré du polynôme
minimal des dérivées logarithmiques des solutions
liouvilliennes de telles équations (travail commun avec
D.~Boucher et F.~Ulmer) puis on présente
une stratégie de recherche du groupe de Galois d'une
équation
en connaissant ses semi-invariants de degré 2 et 4, obtenue
après avoir en particulier complété les travaux
précédents par les cas imprimitif-monomial de la
classification des groupes.
On trouve alors plus efficacement
des semi-invariants produits de formes linéaires. On
s'intéresse aussi aux chutes de degré
de la puissance symétrique quatrième d'une
équation et à des exemples.
Octobre
2004
Vendredi 1er Octobre 2004, 11h00
Patrick Dehornoy (Université
de Caen)
La méthode du retournement
de mot
Résumé.
Le retournement de mot est une methode combinatoire permettant de
travailler avec des monoides ou des groupes definis par des
presentations explicites (et non necessairement abeliens). Dans les
bons cas, a savoir lorsque la presentation satisfait certaines
conditions de completude analogues a celles qui definissent les bases
de Grobner, on obtient en particulier des algorithmes de complexite
quadratique pour la resolution du probleme de mot.
Vendredi 8 Octobre 2004, 10h30
Juan Morales-Ruiz (Barcelone)
A remark about Painlevé
transcendents
The Painlevé transcendents are Hamiltonian
systems that, except for Painlevé I, depend on parameters.
Moreover,
for some values of the parameters they have algebraic or transcendental
``classical" particular solutions. So, in these cases we can try to
apply the Galoisian method to the variational equation along these
particular solutions in order to obtain a non-integrability criteria:
the Hamiltonian system is not completely integrable with meromorphic or
rational first integrals provided the identity component of the Galois
group of the variational equation is non-commutative. Here we obtain
the non-integrability of a discrete family of the Painlevé II
equations by rational first integrals.
Vendredi 15 Octobre
2004, 10h30
Thomas Cluzeau (Université
de Limoges)
Solutions
polynomiales d'équations différentielles linéaires.
Résumé
Le sujet de cet exposé est le calcul des solutions polynomiales
d'Équations Différentielles Linéaires
(É.D.L.).
Dans une première partie, nous rappellerons brièvement
les principales méthodes existantes et nous étudierons
leur complexité.
La deuxième partie présentera un algorithme
entièrement modulaire. Nous évaluerons la pertinence des
informations modulaires que l'on peut obtenir pour le problème
du calcul des solutions polynomiales d'É.D.L.. Nous donnerons la
complexité de notre algorithme et nous la comparerons à
celle des algorithmes existants. Puis, nous exhiberons des classes
d'É.D.L., apparaissant naturellement en théorie de Galois
différentielle, pour lesquelles notre approche modulaire est
bien adaptée. Cette deuxième partie constitue en travail
en collaboration avec Anne Fredet (Lab. STIX,
École polytechnique).
Dans la dernière partie de cet exposé, nous montrerons
comment utiliser les techniques pour le calcul rapide du
$N$-ième terme d'une récurrence linéaire à
coefficients polynomiaux pour obtenir un test efficace de non-existence
de solutions polynomiales non-nulles d'É.D.L.. Cette
troisième partie est un travail réalisé avec Alin
Bostan (INRIA ALGO + STIX) et Bruno Salvy (INRIA ALGO + STIX).
Lundi 25
Octobre, à 10
heures
Soutenance
de thèse de Philippe
Gaillard (IRMAR)
Applications de la
théorie de Galois différentielle aux
équations différentielles linéaires d'ordre 4
Résumé.
Pour les équations différentielles ordinaires
linéaires d'ordre 2 et 3, des algorithmes
de résolution exacte avec des temps de calcul réalistes
existent, se fondant sur une étude préalable
précise des groupes de Galois différentiels potentiels de
ces équations. Plusieurs études de l'ordre 4 ont
déjà eu lieu mais ne concernaient qu'un aspect
particulier de la classification des groupes. Dans cette thèse,
on donne les bornes optimales pour le degré du polynôme
minimal des dérivées logarithmiques des solutions
liouvilliennes de telles équations (travail commun avec
D.~Boucher et F.~Ulmer) puis on présente une stratégie
algorithmique de recherche du groupe de Galois différentiel
d'une équation en connaissant ses semi-invariants de
degré 2 et 4, obtenue après avoir en particulier
complété les travaux précédents par les cas
imprimitif-monomial de la classification des groupes. On trouve alors
plus efficacement des semi-invariants produits de formes
linéaires.
Dans le chapitre 4 de cette thèse, on s'intéresse aux
chutes d'ordre de la puissance symétrique quatrième d'une
équation. Plus précisément, on montre qu'une chute
d'ordre de un implique l'existence d'au moins un semi-invariant de
degré 4, ce qui permet d'obtenir des informations sur le groupe
de l'équation. En cas de chute d'ordre de deux et plus, des
conditions de finitude du groupe sont données par un
théorème de M.F.~Singer.
Dans le chapitre 5, on traite deux exemples. Dans le premier, on
applique la stratégie
algorithmique décrite dans le chapitre 3 en vue de trouver le
groupe de Galois différentiel d'une équation dont on
calcule ensuite les solutions (à l'aide d'une méthode
décrite par F.~Ulmer). Le second est un exemple de
résolution du problème inverse pour le groupe $SO(4,C )$
à l'aide de la méthode décrite par C.~Mitschi et
M.F.~Singer (équation qui n'admet donc pas de solutions
liouvilliennes).
On trouvera en annexe la liste explicite des semi-invariants de
degré 2 et 4 des sous-groupes monomiaux de $SL(4,\C )$.
Vendredi 29 Octobre 2004, 10h30
Fabrizio Caruso
(post-doc à l'IRMAR)
Symbolic
Hypergeometric Summation.
Novembre 2004
Vendredi 5 Novembre
2004, 10h30
Saugata
Basu
(Georgia Tech)
Efficient Algorithms for Computing the
Betti Numbers of Semi-algebraic Sets.
Abstract.
In this talk I will describe some new algorithms for computing the
Betti numbers of semi-algebraic sets. More precisely, I will
describe an algorithm for computing the first few Betti numbers of any
given semi-algebraic set whose complexity is singly exponential in the
dimension. Previously, only the zero-th Betti number was known to be
computable in single exponential time. I will also describe a
polynomial time algorithm for computing certain Betti numbers of sets
defined by quadratic inequalities.
Mercredi 10 Novembre
2004, 16h15, salle 16
Dmitrii Pasechnik (Tilburg University)
Complexity and
algorithms for semi-algebraic sets over quadratic maps
(joint work with Dima Grigoriev)
Abstract:
A semialgebraic set S is said to be defined over a map if S is given by
a formula of the form F(Q(X)), where Q : R^n -> R^k is a polynomial
map and F(Y) is a quantifier-free Boolean formula with polynomial
inequalities (with polynomials of degree at most d belonging to a
subset of R[Y] of size s) as atoms.
We concentrate on a nontrivial and important for applications case when
Q is quadratic.
It turns out that the behavour of S differs rather drastically from the
behavour of a general n-variate semialgebraic set given by degree d
polynomials.
For instance, the sum of the Betti numbers of S is bounded by
(sdn)^O(k), and a similar bound holds for the complexity of sampling in
S (i.e. computing representatives of
the connected components of S).
References:
Polynomial-time computing over quadratic maps I:
sampling in real algebraic sets, by D. Grigoriev and D.V. Pasechnik.
To appear in Computational Complexity, see also
http://arxiv.org/abs/cs.SC/0403008
Décembre 2004
Vendredi 3 décembre, 10h30
Elie
Compoint (Lille)
Factorisation absolue d'opérateurs
différentiels.
Résumé.
Un opérateur est dit absolument irréductible
sur C(x), s'il demeure irréductible sur toute extension
algebrique de C(x).
En utilisant un résultat de descente galoisienne pour les
opérateurs différentiels dû à Katz, on donne
un algorithme de factorisation absolue
pour les opérateurs différentiels définis sur
C(x).
Vendredi 10 Décembre, 10h30
Nicolas
Leroux (Limoges)
Calcul de séries formelles
solutions de systèmes d'edp par une méthode de type
Newton.
Résumé.
Je présenterai une généralisation au cas des
systèmes d'edp dits réguliers d'une méthode
introduite par Geddes pour calculer la série solution d'une EDO
en un point régulier. Cette méthode se prête bien
à des calculs modulaires et à des remontées de
type Hensel. Grace à des techniques de séries majorantes,
on obtient une borne sur les coefficients dans le cas des EDOs. De
telles bornes sont envisageables pour les systèmes
réguliers. Ce travail a été réalisé
en collaboration avec Evelyne Hubert.
Vendredi 17 Décembre, 10h30
Mickaël
Foursov (IRISA)
Approximation
des séries génératrices non linéaires par
des séries rationnelles.
Résumé.
Dans cet exposé, nous parlerons
d'une amélioration de la méthode d'identification et de
modélisation de systèmes dynamiques de Hespel--Jacob,
dans le cas d'une seule entrée. Notre nouvelle méthode
permet de construire, quand c'est possible, l'unique système
bilinéaire de rang minimal qui satisfait toutes les conditions
obtenues au cours de l'identification des coefficients de la
série génératrice du système dynamique. Il
est aussi important de remarquer que maintenant nous pouvons
reconnaître de façon non ambiguë une série
formelle rationnelle de rang r
à partir de l'information obtenue des premières 2r-1 dérivées de la
sortie du système dynamique. Ce travail a été
réalisé avec Christiane Hespel.
Janvier 2005
Février 2005
Vendredi 4
Février, 10h30
Ali
Ayad (IRMAR)
Algorithme
de factorisation absolue de polynômes paramétriques.
Résumé.
Etant donné
un polynôme f à coefficients paramétriques,
l'algorithme partage l'espace des paramètres à des
sous-ensembles constructibles deux à deux disjoints tel que la
factorisation absolue de f est uniforme sur chacun de ces ensembles,
i.e., les coefficients des facteurs absolument irréductibles de
f sont des fonctions rationnelles des paramètres.
On parlera
à la fin de cet exposé sur les applications de cet
algorithme dans de futurs travaux.
Vendredi 11
Février, 10h30
Richard
Leroy (IRMAR)
Minimisation
des polynômes en plusieurs variables par la théorie des
moments,
d'après Lasserre.
Résumé.
Depuis
une dizaine d'années, la programmation semi-définie
positive (SDP) constitue un domaine de recherche très en vogue
en optimisation. Un des principaux objectifs de la programmation SDP
est de fournir des relaxations de problèmes d'optimisation
polynomiale. On obtient ainsi des méthodes numériques
donnant une solution approchée ou des bornes sur les solutions
de problèmes pour lesquels il n'existe pas en
général d'algorithme de résolution exacte
efficace.
Dans ce séminaire, on étudiera le
problème (P) de minimisation d'un polynôme en plusieurs
variables. En 2000, J.B. Lasserre a proposé une
méthode consistant à reformuler ce problème
à l'aide de la théorie des moments. Il obtient ainsi une
suite de relaxations (Q_n), dont les solutions tendent vers le minimum
recherché.
Mars 2005
Vendredi 18 Mars, 10h30
Edward
A. Hirsch (Steklov Institute of
Mathematics, St.Petersburg)
SAT Algorithms: Upper and Lower Bounds
Abstract.
We survey algorithms for the Boolean satisfiability problem (SAT).
Despite SAT is NP-complete, the algorithms for SAT remain a hot topic.
I will survey SAT algorithms that lead to the currently best worst-case
upper bounds and describe the situation with
lower bounds for such algorithms.
Vendredi
25 Mars, 10h30
Mohab Safey El Din
(LIP6)
Efficacité
et complexité de la méthode des points critiques.
Résumé.
Soit
f un polynôme en
n variables à coefficients
rationnels.
Dans un premier temps, nous présenterons un algorithme calculant
au moins un point par composante connexe dans la variété
algébrique réelle définie par
f=0. La complexité de cet
algorithme est exponentiellement meilleure que celle des
précédents, et une analyse fine de la taille de la sortie
permet d'obtenir de nouvelles majorations sur le nombre de composantes
connexes d'une hypersurface dépendant du degré des
composantes de dimension positive du polynôme
f.
Dans un deuxième temps, nous présenterons un algorithme
calculant au moins un point par composante connexe dans le
complémentaire de l'hypersurface définie par
f=0. Celui-ci se fonde sur la
notion de valeur critique généralisée d'un
polynôme introduite par Kurdyka et ses collaborateurs. Une
étape intermédiaire réside dans le calcul des
valeurs critiques généralisées de
f pour lequel nous donnons un
algorithme asymptotiquement optimal. La complexité globale de
notre contribution est elle aussi exponentiellement meilleure que celle
des précédentes.
Avril 2005
Vendredi 8 Avril, 10h30
Claudine
Mitschi (IRMA, Strasbourg)
Approche
constructive du problème de Galois différentiel inverse.
Résumé.
Le problème inverse en théorie de
Galois différentielle est désormais résolu sur
C(t), C un corps algébriquement clos de caractéristique
zéro. La résolution constructive de ce problème
reste cependant un problème ouvert. Via une décomposition
Lévi, on peut réduire le problème aux deux cas
suivants :
- celui d'un groupe algébrique à composante neutre
résoluble : nous avons avec M. Singer donné une solution
constructive dans ce cas (modulo un problème inverse de
théorie de Galois classique sur C(t))
- celui d'un groupe G à composante neutre G0 semi-simple, dont nous donnons avec M.
Singer une solution constructive (modulo, toujours, la
réalisation galoisienne du groupe fini des composantes connexes
de G) quand G0 est de la forme G0 = G_1...G_r, où chaque facteur G_i
est un groupe simple de l'un des types A_l, C_l, D_l, E_6 ou E_8.
Vendredi 29 Avril
Rouchid Bahloul
(Angers/ Post Doc Université de Kobe)
Eventail
de Gröbner local : un résultat polyédral.
Résumé
L'éventail
de Gröbner d'un idéal peut se
définir grossièrement comme suit : deux vecteurs de poids
sur les variables sont declarés équivalents si les
idéaux initiaux associés sont égaux; les classes
d'équivalence forment alors l'éventail de Gröbner.
Cet objet remonte à la fin des années 80. Il fut
initialement associé à un idéal polynomial. On
peut aussi le definir dans le cas d'un idéal différentiel.
C'est un outil important comme on le rappellera, dans le domaine des
D-modules (fonctions b) et les systèmes d'EDP.
Etant donné un idéal dans l'anneau des séries
formelles ou convergentes ou encore dans l'anneau des opérateurs
différentiels à coefficients dans l'un de ceux-ci,
peut-on associer un éventail de Gröbner ?
La réponse est positive et on parle alors d'éventail de
Gröbner local.
Assi et al. (2001) ont traité ce cas mais il n'ont pas
montré que l'éventail de Gröbner est un
éventail polyédral. Dans un travail en collaboration avec
N. Takayama, nous avons montré ce dernier résultat. Nous
avons également proposé un algorithme pour calculer
l'éventail de Gröbner local lorsque les données sont
algébriques.
Mai 2005
Mercredi
4 mai à 14 heures
Soutenance de
thèse de Solen Corvez (IRMAR)
Etude de systèmes polynomiaux :
contributions à la classification d'une famille de manipulateurs
et au calcul des intersections de courbes A-splines.
Vendredi 13 mai, 9h00
Alban Quadrat
(INRIA Sophia Antipolis)
Une
introduction à l'analyse algébrique effective et à
ses applications.
Résumé format pdf
ou résumé format
texte.
Mots-clés:
Etudes des systèmes linéaires d'équations aux
dérivées partielles, systèmes
sous-/sur-déterminés, D-modules algébriques,
bases de Gröbner non-commutatives, théorie du
contrôle, physique mathématique.
Résumé:
L'analyse algébrique a été
développée dans les années 60 afin
d'étudier les systèmes généraux
linéaires d'équations aux dérivées
partielles (EDPs) à coefficients constants ou variables (e.g.,
coefficients polynomiaux, rationnels). L'idée centrale est
d'associer à un système linéaire d'EDPs un module
de présentation finie sur un anneau d'opérateurs
différentiels. Alors, en utilisant la théorie des
modules, l'algèbre homologique, l'analyse fonctionnelle et les
méthodes constructives de l'algèbre effective (e.g.,
bases de Gröbner non-commutatives, bases de Janet), on peut alors
étudier les propriétés intrinsèques de ce
module et les interpréter en termes du système initial
[4].
Le but de cet exposé est de donner des algorithmes effectifs
permettant de reconnaître certaines propriétés des
systèmes d'EDPs sur-déterminés (e.g.,
opérateurs de divergence ou de rotationnel, équations de
Maxwell, équations d'Einstein) à l'aide de la
classification suivante des modules: modules possédant de la
torsion, modules sans-torsion, modules réflexifs, modules
projectifs, modules stablement libres, modules libres [2,3]. Nous
montrerons comment ces propriétés sont reliées
à la possibilité de paramétrer les solutions de
tels systèmes à l'aide de fonctions arbitraires
[2,3].
Finalement, nous illustrerons ces différents résultats
sur des problèmes venant de la théorie du contrôle
(e.g., étude de la contrôlabilité, de l'existence
d'une représentation image, étude du suivi de trajectoire
et de la commande optimale) et de la physique
mathématique (e.g., étude de l'existence de potentiel
pour les équations de Maxwell ou d'Einstein). Des exemples
explicites seront étudiés à l'aide de la librairie OreModule développée
en Maple [1]. Une extension de ces résultats à d'autres
classes d'algèbre d'opérateurs fonctionnels sera aussi
évoquée.
Bibliographie
[1] F. Chyzak, A. Quadrat, D. Robertz, OreModules project,
http://wwwb.math.rwth-aachen.de/OreModules/,
2003.
[2] F. Chyzak, A. Quadrat, D. Robertz, ``Effective algorithms for
parametrizing
linear control systems over Ore algebras'', rapport INRIA 5181,
à paraître
dans Applicable Algebra in
Engineering, Communication and Computing,
2005,
www-sop.inria.fr/cafe/Alban.Quadrat/index.html.
[3] J.-F. Pommaret, A. Quadrat, ``Algebraic analysis of linear
multidimensional
control systems'', IMA Journal of
Control and Information, 16 (1999),
247-260.
[4] A. Quadrat, ``An introduction to the algebraic theory of linear
systems of
partial differential equations'', 2004, www-sop.inria.fr/cafe/Alban.Quadrat/Temporaire.html.
Vendredi
20 Mai, 10h30
Amir Hashemi
(LIP6)
Complexité
du calcul de la base de Gröbner.
Résumé.
Dans la première partie de cet
exposé, on présente une amélioration de la borne
des complexités des algorithmes dont la complexité
dépend
- du théorème de
Bézout,
- de la dimension de
l'espace vectoriel des polynômes ayant la borne de Macaulay comme
degré.
Dans la deuxième partie, on présente un algorithme pour
calculer la base de Gröbner d'un idéal
zéro-dimensionnel en temps simplement exponentiel en max{S,D^n}
ou S est la taille d'entrée, et D est la moyenne
arithmétique des degrés des polynômes
d'entrée. Cet algorithme est présenté de
manière à pouvoir l'étendre aux suites
régulières de dimension positive en coordonnées
génériques.
Vendredi
27 Mai, 10h30
Richard Leroy (IRMAR)
Polynômes
positifs modulo l'idéal engendré par leur gradient.
Application à la minimisation.
Résumé.
Le problème de la minimisation polynomiale est en
général NP-dur.
Récemment s'est développée une nouvelle approche,
numérique, conduisant
à des solutions approchées. L'utilisation des sommes de
carrées de
polynômes au lieu des polynômes positifs, y est cruciale.
La difficulté
majeure est qu'un polynôme positif n'est pas forcément une
somme de
carrés de polynômes.
Dernièrement, Sturmdels, Demmel & Nie ont proposé une
nouvelle
approche, pour laquelle la situation est plus favorable : sous
certaines conditions, un polynôme positif est une somme de
carrés dans
le quotient de l'anneau des polynômes pour l'idéal
engendré par son
gradient.
Après avoir donné la preuve de ce résultat, on
l'appliquera à la minimisation polynomiale.
Juin 2005
Vendredi
3 Juin, 10h30
Karim Belabas (Orsay)
Factorisation
de polynômes univariés sur un corps global
(en
collaboration avec Mark van Hoeij, Jürgen Klüners, et Allan
Steel)
Résumé.
Vers 2000, Mark van Hoeij a proposé un
algorithme de factorisation dans $\mathbb{Q}[X]$, qui repose sur le
même principe que Berlekamp-Zassenhaus (borner les facteurs,
factoriser sur un $\mathbb{Q}_p$ convenable puis recombiner les
facteurs), mais utilise la réduction de réseaux pour
améliorer drastiquement la dernière phase combinatoire.
Typiquement, quelques secondes pour une centaine de facteurs locaux.
J'expliquerai cette idée, comment elle se
généralise, et comment on en déduit un nouvel
algorithme qui factorise un polynôme univarié sur un corps
global en temps polynomial. La complexité prouvée est la
même que celle obtenue par Lenstra, Lenstra et Lovácz en
1982, le comportement pratique très nettement meilleur.
Mercredi
15 juin à 14 heures
Soutenance de thèse de
Gwénolé Ars (IRMAR)
Application
des bases de Gröbner à la cryptographie.
Vendredi
17 Juin, 10h30
Klaus Meer (University of
Southern Denmark, Odense)
Complexity theory over the reals and
probabilistically checkable proofs.
Résumé
(pdf).
Probabilistically
checkable proofs (PCPs) represent one of the most important
recent areas in theoretical computer science . The idea is to make
verification proofs of NP-problems more stable: Reading only a constant
number of data units in such a potential proof will be sufficient
to detect faults with high probability.
In this talk we introduce the PCP notion for the real number model
of Blum, Shub, and Smale. We then study the existence of
certain such ``transparent''
proofs for the class NP$_{\mathbb R}$
of real number decision problems verifiable in polynomial time.
Du 27 Juin au 1er Juillet
Workshop "Algorithms in real algebraic geometry and applications"
Ile de Ouessant, France.