Vendredi 7 Novembre
2003 , 10h30
Magali Bardet (LIP6)
Complexité
du calcul de base de Gröbner pour des systèmes
semi-réguliers surdéterminés.
(travail en commun avec Jean-Charles
Faugère et Bruno Salvy)
Résumé (voir aussi fichier .ps):
Nous nous intéressons au
problème de la complexité du
calcul d'une base de Gröbner pour des systèmes
``suffisamment
génériques'' et surdéterminés. Par
exemple, pour des systèmes dont
les coefficients ont été tirés au hasard,
ou pour des systèmes dont
les générateurs ont des coefficients
``indépendants''. Notons que
l'exemple de Mayr-Meyer, dont la complexité est doublement
exponentielle, n'appartient pas à la catégorie des
systèmes
``suffisamment génériques''.
Nous commençons l'exposé par des rappels sur les
suites régulières
et sur leurs propriétés. Pour un système de
$m$ équations à $n$
inconnues avec $m\le n$, la définition de suite
régulière convient
comme définition mathématique de ``suffisamment
générique'', et la
complexité du calcul d'une base de Gröbner est bien
comprise. Pour
de telles suites, on connaît leur série de Hilbert
et leur
régularité, et si la suite est en position de
Noether et que l'on
utilise l'ordre DRL (Degré Reverse Lexicographique), on
peut prévoir
exactement le comportement de l'algorithme de calcul de base de
Gröbner F5 de Jean-Charles Faugère, et donner la
complexité
(arithmétique) globale du calcul. De plus, on peut
montrer que
``presque toute suite'' est une suite régulière
(l'ensemble des
suites régulières est un ouvert de Zariski non
vide dans l'ensemble
des suites possibles, si on a fixé le nombre de
générateurs et leurs
degrés, ainsi que le nombre de variables).
Cependant, dans de
nombreuses applications, les systèmes rencontrés
sont surdéterminés,
et les études sur les suites régulières ne
s'appliquent plus (en
particulier, il n'existe plus de suites
régulières).
Nous donnons une définition mathématique de
``suffisamment
générique''. Nos définitions de suites
semi-régulières et de degré
de régularité étendent la notion de suite
régulière et de régularité
aux suites surdéterminées. Nous montrons que
pour des suites
semi-régulières, on peut prévoir les
tailles exactes de chaque
matrice intervenant dans la version matricielle de l'algorithme
F5.
Cela nous permet de calculer la série de Hilbert, le
degré de
régularité et le coût (arithmétique)
global du calcul de la base de
Gröbner, pour tout ordre gradué par le
degré. Nous donnons un
algorithme qui, étant donnés des entiers
$m,n,d_1,\ldots,d_m$ calcul
le degré de régularité d'une suite
semi-régulière de $m$ polynômes
en $n$ variables de degrés respectifs
$d_1,\ldots,d_m$. En
utilisant des techniques d'analyse asymptotique (séries
génératrices, méthodes du point col et des
points cols coalescents)
nous calculons un développement asymptotique de ce
degré en fonction
du nombre de variables. Ainsi, pour une suite de $2 n$
polynômes
quadratiques en $n$ variables à c{\oe}fficients entiers,
le degré de
régularité est \Dmax$\sim 0.085786\,n+
1.0415\,n^{1/3}- 1.4697+
1.7130 \,\frac 1 {n^{1/3}} + o\left( {\frac {1}{n^{1/3}}}
\right)$
(ainsi \Dmax$\sim n/11.657$ est une bien meilleur borne que la
borne
de Macaulay $\sim n$ que l'on obtient si l'on ne tient pas
compte de
la surdétermination). Nous donnons la valeur explicite de
chaque
c{\oe}fficient, et le coût global du calcul est
$\binom{n+\text{\Dmax}-1}{\text{\Dmax}}^{\omega}$ où
$\omega$ est le
coefficient d'algèbre linéaire. Nous
prouvons que pour $m\le n+1$,
``presque toute'' suite est une suite
semi-régulière, et nous le
conjecturons dans les autres cas.
Ces techniques s'appliquent également (moyennant quelques
adaptations) au calcul d'une base de Gröbner pour un
système modulo
deux comportant les équations de corps
$x_1^2-x_1,\ldots,x_n^2-x_n$
(voir l'exposé
du séminaire de Cryptographie l'après-midi).
Ce type de système a de nombreuses applications dans le domaine
de la cryptographie.
Vendredi 28 Novembre 2003 , 10h30
Solen Corvez (IRMAR)
Utilisation
de la théorie des invariants
pour calculer les points d'inflexion réels d'une cubique
(d'après un papier de Falai Chen et Wenping Wang).
Résumé:
Cet exposé est basé sur un article de Falai Chen et
Wenping Wang dans lequel
ils décrivent un algorithme permettant de calculer les points
d'inflexion réels
d'une cubique sans résolution de système
d'équations polynomiales.
Cet algorithme suit une idée de Hilbert basée sur la
théorie des invariants
pour calculer les points d'inflexion d'une forme ternaire de
degré trois.
Dans un premier temps, de manière à rendre
compréhensible le résultat de Hilbert,
j'expliquerai comment obtenir des invariants et des covariants
d'un polynôme
homogène de degré donné en introduisant la
méthode symbolique de Cayley.
Ensuite je présenterai le travail des auteurs dont
l'originalité est de classifier
les cubiques selon des relations portant sur leurs invariants
puis d'utiliser
la configuration particulière des points d'inflexion d'une
cubique pour n'avoir
à calculer parmi eux que les points réels.
Vendredi 28 Novembre 2003 , 14h00
Sidi Mohamed Sedjelmaci
(Paris 13, LIPN)
Algorithme
d'Euclide accéléré.
Résumé:
Nous présentons un nouvel algorithme pour le pgcd de deux
entiers ou deux polynômes. Il est basé sur une
procédure du type "half-gcd", mais, contrairement à celle
de Schonhage, notre procédure n'est pas récursive et
ainsi, nousévitons plusieurs appels récursifs
pénalisants. La complexité au pire des cas de notre
algorithme est aussi en $O(n \log^2 n \log \log n)$ pour deux entiers
de
$n$ bits, cependant, il commence directement par les bits de poids les
plus forts et réduit d'un demi mot mémoire à
chaque
itération. Il est de plus, valable meme pour les entiers de
petite ou moyenne taille.
Vendredi 12 Décembre 2003,
10h30
Soutenance de thèse de Thierry Zell (Georgia
Institute of Technology):
Etude
quantitative des ensembles semi-pfaffiens.
Résumé :
Les fonctions pfaffiennes ont été définies
par Khovanskii. Elles
forment une large classe de fonctions analytiques, et ont un
comportement quasi-polynomial dans le domaine réel.
En particulier, de façon analogue au cas semi-algébrique,
tout
ensemble défini à l'aide de fonctions pfaffiennes a des
caractéristiques topologiques très simples. Les nombres
de Betti
(i.e. le rang des groupes d'homologie singulière) d'un tel
ensemble
sont toujours fini.
Dans cette thèse, on s'est attaché à donner des
bornes explicites à
cette complexité topologique. On considère bien sûr
le cas des
ensembles semi-pfaffiens (c'est-à-dire ceux définis par
une
condition de signe booléenne sur des fonctions pfaffiennes), mais
plus généralement, on s'intéresse aux ensembles de
la structure
o-minimale engendrée par les semi-pfaffiens.
Vendredi 19 Décembre 2003 , 10h30
Sadjia Aït-Mokhtar (LMA, La
Rochelle)
Sur une équation de Riccati
singulièrement perturbée.
Résumé (voir aussi resumé .ps):
L'objet principal est l'étude du mouvement et des bifurcations
des singularités
des solutions d'une équation différentielle
singulièrement perturbées
$\epsilon u'=\Phi(z,u,a,\epsilon)$ en fonction du
paramètre $a$.
On montre dans le cas d'une équation de Riccati que les valeurs
de surstabilité
sont des singularités logarithmiques de la fonction multiforme
"Indicatrice des pôles"
qui à toute valeur du paramètre $a$ associe les
pôles de la solution distinguée.
Vendredi 23 Janvier 2004 , 10h30
Sergei Evdokimov
Recognizing and isomorphism testing
circulant graphs in polynomial time.
Résumé:
We recognize the circulant graphs and find canonical labeling for them
in polynomial time. The algorithm also includes finding a cycle base of
an arbitrary solvable permutation group. The correctness of the
algorithm is based on a new result on the structure of Schur rings over
a finite cyclic group.
Vendredi 30 Janvier 2004, 10h30
Fabrice Rouillier (INRIA
Rocquencourt)
Résolution des systèmes
d'égalités et d'inégalités polynomiales
dépendant de paramètres.
Résumé (voir aussi resumé .ps):
Nous supposons que l'on veut étudier un
système de la forme
$$\{p_1=0,\ldots p_s=0,f_1>0,\ldots f_s>0 \}$$ où les
polynômes $p_i,f_j$ appartiennent à $K[U_1,\ldots
U_d,X_{d+1},\ldots X_n]$, $K$ étant un coprs de
caractéristique zéro (ordonné dans le cas
réel). On notera ${\cal E}=\{p_1,\ldots p_s \}$, ${\cal
F}=\{f_1,\ldots f_l \}$, $V_C\subset C^n$ la variété
définie par les zéros de $I=<p_1,\ldots p_s >$,
${\cal C}=\{x\in \C^n p_1=0,\ldots p_s=0,f_1\neq 0,\ldots f_s\neq 0\}$
et ${\cal S}=\{x\in R^n p_1=0,\ldots p_s=0,f_1 > 0,\ldots f_s >
0\}$, où $R$ est un corps réel clos contenant $K$ et $C$
la cloture algébrique de $C$.
Les systèmes paramètrés à résoudre
dans la plupart des applications sont en général tels que
l'extension de l'idéal $I=<p_1,\ldots ,p_s>$ dans
$K(U_1,\ldots U_d)[X_{d+1},\ldots X_n]$, que nous noterons $I^e$, soit
zero-dimensionnelle. Nous appellerons $[U_1,\ldots U_d,X_{d+1},\ldots
X_n]$ l'ensemble des indéterminées du problème,
$[U_1,\ldots U_d]$ l'ensemble des paramètres et $[X_{d+1},\ldots
X_n]$ l'ensemble des variables.
La plupart des algorithmes permettant d'étudier ce type de
systèmes (nombre de racines en fonction des paramètres,
paramétrisations des solutions, etc.) calculent
systématiquement une décomposition de l'espace des
paramètres ($C^d$ ou $R^d$) contenant une collection dense
d'ouverts dont l'image réciproque par la projection canonique
sur
l'espace des paramètres ($\Pi_U:C^n\longrightarrow C^d$) est un
revètement analytique.
Nous appellerons variété discriminante large du
système (associée à $\Pi_U$), toute
$K$-variété algébrique (zéros de
polynômes à coefficients dans $K$) induisant une partition
de l'espace des paramètres constituée de la
variété elle même et d'ouverts connexes (maximaux
pour l'inclusion) ${\cal U}_1,\ldots {\cal U}_k$ tels que~:
\begin{itemize}
\item $(\Pi_U^{-1}({\cal U}_i)\bigcap V_C,Pi_U)$ soit un
revêtement analytique de ${\cal U}_i$ pour tout $i=1\ldots k$;
\item les éléments de ${\cal F}$ sont de signes constants
sur $\Pi_U^{-1}({\cal U}_i)\bigcap V_C$ pour tout $i=1\ldots k$;
\end{itemize}
La décomposition cylindrique algébrique adaptée
à ${\cal E}\bigcup {\cal F}$ permet de calculer
explicitement une variété discriminante large de ${\cal
C}$ ou ${\cal S}$, pourvu que les calculs aient été
effectués en traitant les paramètres $U_1,\ldots ,U_d$ en
dernier : il suffit de considérer la variété
algébrique définie par l'ensemble des zéros des
polynômes obtenus après la $n-d$-ieme étape de
projection. Elle n'est absolument pas optimale en termes de nombres
d'ouverts produits puisqu'elle contient, entre autres, des
variétés discriminantes pour tous les systèmes
d'égalités et d'inégalités que l'on peut
construire en utilisant les polynômes de ${\cal E}\bigcup {\cal
F}$ (rappelons que la CAD fournit, dans tous les cas, une
stratification
en cellules de $\R^n$, adaptée à une famille de
polynômes).
La plupart des autres techniques de calcul, du moins, celles qui ne
considèrent pas le problème récursivement en
fonction des variables, utilisent massivement le fait que, sous
certaines hypothèses assez peu restrictives, $I^e$ est
zéro-dimensionnel.
C'est le cas des techniques de type Hermite ou des calculs de
paramétrisations qui produisent des résultats directement
exploitables, mais c'est souvant le cas également des
algorithmes
de décomposition en idéaux équi-dimensionnels,
l'équi-dimensionalité de $V_C$ étant très
souvant un prérequis pour beaucoup de méthodes). Ces
méthodes calculent et exploitent de façon visible ou non
une variété discriminante le plus souvant de type
"large".
Par exemple, les techniques basées sur les "Comprehensive
Gr\"obner bases", calculent une variété discriminante
large. Elles ne sont pas optimales puisqu'elles contiennent les valeurs
de paramètres dépendant de la stratégie
utilisée. Plus précisément, on retrouvera (au
moins) les valeurs de mauvaise spécialisation de bases de
Gröbner.
Les paramétrisations en tous genres calculent explicitement ou
implicitement elles aussi des variétés discriminantes
larges. La encore, celles -ci ne sont pas optimales puisqu'elles
dépendent de la stratégie utilisée. En effet,
elles
dépendent du choix d'un polynôme "séparant",
polynôme minimal ou caratéristique d'un
élément primitif $t$ de $\Q(U_1,\ldots
,U_d)[X_{d+1},\ldots ,X_n]$ : la variété
représentant les valeurs exceptionnelles des paramètres
à exclure pour que la paramétrisation soit valide est une
variété discriminante large. Elle contient, en
général, le discriminant et le terme de tête de ce
polynôme incluant, en particulier, les valeurs des
paramètres telles que la spécialisation de $t$ en ces
paramètres ne sépare pas les zéros de la
spécialisation du système (en ces paramètres).
Dans la première partie, nous définissons une notion de
variété discriminante stricte. Cette
variété
est en particulier une variété discriminante large
mais elle est uniquement définie pour un système et une
projections donnés. Nous montrerons qu'elle est optimale dans
tous les cas (resp. dans le pire des cas) dans le cadre complexe (resp.
dans le cadre réel) pour le nombre d'ouverts contenus dans la
partition qu'elle induit.
En particulier, elle est indépendante de tout algorithme de
calcul.
Dans la deuxième partie, nous proposons plusieurs
stratégies pour calculer la variété discriminante
associée à un système paramètré
n'utilisant que des outils connus (ensembles triangulaires, bases de
Gröbner). Ce type de calcul dépendant fortement des
propriétés des systèmes étudiés
(equi-dimensionels ou non, ideaux radicaux ou non), nous proposons un
algorithme adaptatif ayant le bon goût de ne pas supposer que
l'on
est systématiquement dans la plus mauvaise des situations. En
d'autres termes, des tests simples permettent à tout moment
d'adapter la stratégie de calcul et d'utiliser les outils les
plus efficaces possibles.
La troisième partie est dédiée à
l'utilisation de la variété discriminante pour
répondre à quelques questions pratiques (nombre de
zéros réels en fonction des paramètres,
stratification de $V_C$, etc.).
Vendredi 27 Février 2004 , 10h30
Emmanuel Briand (PostDoc
Santander)
Le calcul des équations de Brill.
Résumé:
Dans l'espace des polynômes homogènes de degré N en
n variables à
coefficients complexes, les produits de formes linéaires forment
une
sous-variété algébrique fermée. Le
problème est de trouver un système
d'équations qui la définissent.
Brill et Gordan ont donné une solution dans le cadre de la
théorie des
invariants. Leur système d'équations est formé par
les coefficients d'un
grand polynôme, la covariant de Brill.
Je présenterai la démarche de Brill et Gordan; je
montrerai comment
effectuer le calcul du covariant efficacement, en utilisant les
simplifications mises à disposition par la théorie
classique des
invariants; enfin je présenterai les calculs effectués
par ordinateur.
Vendredi 5 Mars 2004 , 10h45
Philippe Trébuchet (LIP6)
Théorème
de Bézout bi-homogène fort, optimisation
algébrique et
algorithmes de la géométrie réelle.
(travail en commun avec Mohab Safey El Din)
Résumé:
Dans cet exposé,
on s'interressera au calcul de points critiques d'une fonction
polynomiale. Précisément, soit une famille de
polynômes $(f_1, \ldots, f_s) \in \Q[X_1, \ldots, X_n]$
engendrant
un idéal radical et $V \subset \C^n$ la variété
algébrique, qui est supposée lisse, associée
à cet idéal. On s'intéresse au calcul des points
critiques d'une application polynomiale $f \in \Q[X_1, \ldots, X_n]$
restreinte à $V$ dans le cas o\`u le lieu critique est
supposé zéro-dimensionnel. Ces points critiques sont
caractérisés algébriquement par une chute de rang
d'une certaine matrice jacobienne. De cette caractérisation, les
points critiques peuvent être définis comme solutions du
système algébrique constitué de $f_1, \ldots, f_s$
et de certains mineurs de la jacobienne mentionné
précédement, ou bien comme
projections de solutions du
système de Lagrange. La première formulation n'est
valable
que dans le cas où $V$ est équi-dimensionnelle. On
montrera qu'elle ne permet pas d'évaluer finement le nombre de
points critiques à calculer, la borne de Bézout classique
étant trop pessimiste. La seconde formulation (système de
Lagrange) est valable dans les cas non-équi-dimensionnels et sa
structure bi-homogène permet de donner des bornes optimales (car
atteintes dans le pire des cas) sur le nombre de points critiques (une
fois démontré un théorème de Bézout
bi-homogène fort). Nous nous intéressons ensuite à
l'application de ce résultat dans le cadre de l'étude des
solutions réelles des systèmes algébriques de
dimension positive. Dans un premier temps, nous
généralisons l'algorithme proposé par Safey (LIP6,
UPMC) et Schost (STIX, Ecole polytechnique) à ISSAC'03 au cas
non-équi-dimensionnel, en montrant que tous les calculs qui y
sont effectués sont des calculs de points critiques et en
profitant des propriétés du système de Lagrange.
Ensuite, en évaluant la sortie de cet algorithme, nous
démontrons de nouvelles bornes pour le nombre de composantes
connexes du lieu réel d'une variété
algébrique lisse. Nous utiliserons aussi ces résultats
pour comparer les sorties dans les pires cas de quelques algorithmes
récemment proposés pour le calcul d'au moins un point par
composante connexe. Nous terminerons en détaillant quelques
perspectives de ce travail.
Vendredi 26 Mars 2004 , 10h30
Nicolay Vassiliev (Steklov Inst. of Math. St.
Petersburg)
Topology of
monomial orderings and universal Groebner bases
Résumé :
We describe topological structure of the spaces of all admissible ad
weak
admissible Monomial orderings. For each ideal in the ring of
polynomials we can
consider Groebner base as a function on the space of monomial orderings.
The theorem of Robbiano about finiteness of elements of universal
Groebner
base of an ideal can be considered from this point of view as a
consequence of the fact that the space of all monomial orderings is
compact.
We define Young diagrams related to the polynomials and prove a
generalization of Dickson lemma for Young diagrams , that give us an
effective way to solve membership problem for the universal Groebner
base. We also give an
algorithmic charachterization of all elements of the universal Groebner
base .
Vendredi 2 Avril 2004 , 10h30
Olivier Ruatta (INRIA, Sophia)
Approximer toutes les racines d'une
equation algébrique
par intégration de champs de vecteurs.
Résumé :
Cet exposé présente une nouvelle approche pour le calcul
d'approximation de toutes les racines d'un poynôme à
coefficients complexes. Cette approche repose sur un analogue continu
de
la méthode de Weierstrass (ou de Dochev ou de Durand-Kerner). Il
est organisé comme suit :
Dans un premier temps nous rappelons brievement la construction de
l'itération de Weierstrass. Nous utilisons alors cette
itération pour décrire un ouvert dense d'un espace dont
les points s'identifient à la liste des racines des
polynômes d'un degré donné et un champ de vecteurs
sur cet ouvert. Nous montrons que les seules singularités de ce
champ de vecteurs correspondent à la liste des racines du
polynôme à résoudre. Nous montrons ensuite que
toute
orbite de ce champ à une des singularités dans sa
fermeture. Dans un deuxième temps, nous montrons
comment approximer une de ces singularités (et par
conséquent les racines cherchées) par deux types de
méthodes : une intégration numérique (de type
méthode d'Euler par exemple) ou par une intégration
semi-formelle (développement en série par un
opérateur de Newton et continuation afin d'appoximer la solution
du système différentiel associé au champ de
vecteur).
Enfin nous conclurons en montrant les liens de cette
méthode avec des méthodes dites "par homotopie" ou "suivi
de chemin". Nous expliquerons en quoi notre approche est meilleure
(certification de convergence, ...). Ensuite nous donnerons des
idées sur la façon d'évaluer la complexité
de telles méthodes.
Vendredi
23 Avril 2004 , 10h30
Marius van der Put
(Groningen)
Descent theory
for linear differential equations
Abstract :
A rather algebraic question is: Let a linear differential equation be
given over a large differential field. Does it come from a differential
equation over a smaller field ?
For geometric objects like curves and abelian varieties descent theory
gives answers. Here we develop descent for linear differential
equations and linear difference equations. Analytic properties of
differential (or difference) equations and skew fields enter the
picture.
Vendredi
14 mai 2004, 10h30
José-Luis Martins (INRIA Rocquencourt)
On Galois theories for overdetermined systems of linear partial
differential equations.
Abstract :
The differential Galois theory of linear ODEs generalises to
overdetermined systems of linear partial differential equations. We
discuss some particular aspects of the direct and inverse problems for
Janet bases of order two over an affine surface.
We will also sketch the link with Malgrange's theory of Galois
groupoids for foliations as well as the unexpected role played by the
Korteweg deVries and Scroedinger's equations in this context.
Vendredi
28 mai 2004, 10h30
Guénaël Renault
(LIP6)
Calcul
d'une base triangulaire d'un idéal des relations.
Améliorations
d'une méthode modulaire proposée par
K. Yokoyama.
Résumé:
À la fin de son article "A modular method for computing the
Galois groups of polynomials" (1997), K. Yokoyama propose une
méthode pour le calcul de l'idéal des relations entre les
racines d'un polynôme f à coefficients rationnels.
Cette méthode est basée sur la résolution de
systèmes linéaires et a pour hypothèse de
départ, la connaissance de l'action du groupe de Galois de f sur
des approximations p-adiques des racines de f. Dans cet exposé
nous montrerons comment une étude plus fine des données
du problème, permet d'améliorer cette méthode en
réduisant le nombre et la taille des systèmes à
résoudre.
Vendredi
11 juin 2004, 10h30
Willi Geiselmann (Universitaet Karlsruhe)
Attacking
a Polynomial Based Cryptosystem: Polly Cracker
Résumé:
Recently Fellows and Koblitz proposed a public key cryptosystem
called Polly Cracker. In this system the public key consists of a
finite set of multivariate polynomials with coefficients in some
finite field, and the secret key consists of a common zero of these
polynomials.
In this talk some `structural' weaknesses in Polly Cracker's
encryption procedureare shown. In particular it will be demonstrated
that with the parameters considered in Koblitz's book it is often
possible to reveal the private key easily.
Furthermore we show that the system is very vulnerable against chosen
ciphertext attacks.
Vendredi
2 juillet 2004, 10h30
Jean-Claude Raoult
(IRMAR)
Les
beaux ordres : application à la base de Groëbner
universelle.
Résumé :
Les beaux ordres tiennent le milieu entre les ordres bien fondés
(n'admettant pas de suite infini décroissante) et les bons
ordres (qui de plus sont totaux). On montrera quelques
propriétés de ces ordres dont l'une, similaire
à un théorème de Higman, permet de déduire
facilement l'existence d'une base de Grœbner «universelle»
contenant toutes les bases de Grœbner d'un ideal.
