irmar


Séminaire de
Calcul Formel et Complexité




Année 2004-2005

Équipe 
Séminaire de
calcul formel et complexité


Septembre 2004

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.