Archives
du séminaire de calcul formel et complexité
2012-2013
Vendredi 28 septembre 2012
Jacques-Arthur Weil (XLIM, Limoges)
Intégrabilité de systèmes hamiltoniens : une version effective du
critère de Morales-Ramis-Simo
(travail commun avec Ainhoa Aparicio)
Le critère de Morales-Ramis-Simo permet de tester
l'intégrabilité ou non de systèmes dynamiques hamiltoniens en étudiant
les équations variationelles obtenues en étudiant le comportement de
trajectoires proches d'une trajectoire connue. Techniquement, il s'agit
de tester si ces équations (de grands systèmes différentiels linéaires)
ont un groupe de Galois différentiel virtuellement abélien.
Nous montrerons comment cette condition, d'apparence bien abstraite,
peut-être testée effectivement en utilisant une technique de réduction
de systèmes différentiels linéaires à une forme sur laquelle l'algèbre
de Lie du groupe de Galois se lit bien.
L'exposé se voudra auto-contenu ; nous utiliserons
essentiellement des
idées simples sur les algèbres de Lie et de l'algèbre linéaire
classique.
Vendredi 5 octobre 2012
Alexandre Le Meur
Certificats de positivité pour plusieurs polynômes en une seule variable
Vendredi 19 octobre 2012
Daouda Niang Datta
Caractérisation de type Hurwitz des Systèmes Commutés Planaires
Globalement Uniformément Asymptotiquement Stables
My talk will focus on recent results concerning the stability problem
for the planar linear switched system x'(t) = u(t) A x(t) + (1 − u(t))
Bx(t) , x = (x1, x2) in R2 where the real matrices A, B are Hurwitz and
for t>0 u(t) in {0,1} is a measurable function.
We give a Hurwitz like characterization of globally uniformly
asymptotically stable planar switched systems. We will also give a
"practical" version of the main result in [NS] using real algebraic
geometry tools.
This new approach give a Hurwitz like characterization of switched
systems which share a same strict or large common quadratic Lyapunov
function and simplify the main result in [BBM].
References :
- [BBM] M. Balde, U. Boscain, P. Mason, A note on stability conditions
fo planar switched systems , international journal of control, Vol 82,
n 10, 1882-1888, (2009).
- [NS] R. Shorten and K. Narendra. Necessary and sufficient conditions
for the existence of a common quadratic Lyapunov function for two
stable second order linear time-invariant systems. In Proceedings 1999,
American Control Conf., pages 1410-1414, 1999.
- [BBMZ ]M. Benaïm, S. L. Borgne, F. Malrieu and P. A. Zitt "On the
stability of planar randomly switched systems"
Vendredi 9 novembre 2012
Tristan Vaccon (IRMAR)
Algorithme F5 matriciel et évaluation de sa perte de précision.
Application vers un calcul de base de Gröbner p-adique.
Jean-Charles Faugère a proposé en 2002 un nouvel algorithme de calcul
de bases de Gröbner dont le principe, étudié ensuite par Magali Bardet
en 2004, est entièrement matriciel : l'algorithme F5 matriciel. Il se
trouve à ce jour parmi les algorithmes les plus rapides pour le calcul
d'une base de Gröbner.
Après une présentation de cet algorithme, nous verrons qu'il peut être
adapté pour étudier le calcul d'une base de Gröbner de polynômes connus
de manière approchée, et en particulier, contrôler les pertes de
précision dans ce calcul.
On s'intéressera plus particulièrement au cas du calcul d'une base de
Gröbner sur Q_p.
Références :
Jean-Charles Faugère. A new efficient algorithm for computing Gröbner
bases without reduction to zero (F5). In Proceedings of the 2002
international symposium on Symbolic and algebraic computation, ISSAC
'02, pages 75-83, New York, NY, USA, 2002. ACM.
M. Bardet, "Étude des systèmes algébriques surdéterminés. Applications
aux codes correcteurs et à la cryptographie", thèse de doctorat,
Université Paris VI, Décembre 2004.
Mardi 20 novembre 2012 à 14h00 en salle des thèses, bâtiment 2A, Campus
de Beaulieu.
Soutenance de thèse de Matthieu Legeay
Titre : "Utilisation du groupe de permutations d'un code correcteur
pour améliorer l'efficacité du décodage"
Vendredi 23 novembre 2012, exceptionnellement deux exposés, à 10h30 et
à 11h30
--10h30 : Clément Pernet (Université Joseph Fourier, Grenoble, LIG)
Adaptive decoding for dense and sparse evaluation/interpolation codes
We will present recent work on evaluation-interpolation error
correcting codes. It is motivated in
the study of algorithm based fault tolerance (ABFT) applied to parallel
exact linear algebra.
Indeed evaluation/interpolation schemes allow to split the
computational load of one problem into
several independent tasks, making the problem embarassingly parrallel.
In the context where soft-errors occur during the computation of some
of these tasks, the
evaluation/interpolation codes make it possible to still recover the
result provided that some
amount of redundant information has been computed.
In a first part we will focus on the interpolation of dense polynomials
with errors, and their
equivalent over the ring of integer: the CRT-codes (Chinese Remainder
Theorem).
We will introduce a more general error model allowing to derive tighter
bounds on the error
correction capacities of such codes. Then we will describe some
improvements making the error
correction capacity adaptive with respect to the exact amount of
information of the result to be
computed.
In a second part we will focus on the interpolation of sparse
polynomials with errors. After proving
a lower bound on the required number of evaluation points, we will
present a unique decoding algorithm matching that bound and a
list-decoding variant of it, with a lesser requirement on the number of
evaluations.
--11h30 : Ilya Dumer (University of California at Riverside)
Covering a sphere with spheres: Rogers bound revisited.
Given a sphere of any radius in an n-dimensional Euclidean
space, we study the coverings of this sphere with unit spheres of
radius 1. Our goal is to design a covering of the lowest covering
density, which defines the average number of unit spheres covering a
point in a bigger sphere. For growing n, we obtain the covering density
of the order (n ln n)/2 or less. The techniques combine
random-coding
arguments with new "porous" covering design and geometric
estimates.
This new bound gives the lowest covering density known to date and is
half the order n ln n established in the classical Rogers bound of 1956.
Vendredi 7 décembre 2012
Christophe Tran (IRMAR)
Calcul de couplages sur courbes elliptiques via les Elliptic Net,
relations avec les fonctions thêta.
Dans les années 2000, l'utilisation des couplages en cryptographie a
permis le développement de nombreux protocoles . Jusqu'à récemment, le
calcul des couplages reposait exclusivement sur l'algorithme de Miller.
En 2007, Katherine Strange proposa une méthode originale de calcul du
couplage de Tate, basée sur l'utilisation d'un outil provenant de
la
théorie des suites récurrentes, les elliptic nets. Après avoir étudié
cet algorithme, nous examinerons les liens profonds entre la théorie
des elliptic net et celle des fonctions thêta. En particulier, on verra
que la formule du couplage de K. Strange est un cas particulier de la
formule donnée par David Lubicz et Damien Robert.
Vendredi 18 janvier 2013
Pierre-Jean Spaenlehauer (University of Western Ontario/INRIA)
Résolution de systèmes polynomiaux structurés et applications en
Cryptologie et en Géométrie Réelle.
Les systèmes polynomiaux multi-homogènes, déterminantiels et
booléens jouent un rôle prépondérant dans plusieurs applications en
Cryptologie, en Géométrie Réelle et en Optimisation. Dans cet exposé,
par des méthodes de calcul de bases de Gröbner et sous des hypothèses
de généricité sur les coefficients de ces systèmes, je présente de
nouvelles bornes de complexité asymptotique pour leur résolution :
- dans le cas déterminantiel et dans le cas bilinéaire, ces
bornes
permettent d'identifier des sous-familles de systèmes pour lesquelles
la complexité de résolution est polynomiale en le nombre de solutions ;
- pour les systèmes quadratiques booléens, un nouvel algorithme
de
résolution est proposé. Pour un système de n équations en n variables,
l'espérance de la complexité d'une variante probabiliste est O(2^(0.792
n)) sous des hypothèses algébriques sur le système d'entrée, ce qui
permet de résoudre exponentiellement plus rapidement que par recherche
exhaustive.
L'obtention de ces bornes passe par une analyse de la structure
algébrique de ces systèmes ; ceci conduit à des formules explicites
pour la série de Hilbert générique des idéaux associés. Cette analyse
sera illustrée par des applications en Cryptologie (cryptanalyse de
MinRank, HFE et QUAD) et en Géométrie Réelle (calcul de points
critiques).
Travaux commun avec Jean-Charles Faugère et Mohab Safey El Din
(systèmes déterminantiels et multi-homogènes) et avec Magali Bardet,
Jean-Charles Faugère et Bruno Salvy (systèmes booléens).
Vendredi 25 janvier 2013
Romain Basson (IRMAR)
Algèbre d'invariants des formes binaires en
caractéristique positive
Le développement d'une algorithmique pour les espaces de
modules de courbes hyperelliptiques (en petit genre) peut s'envisager
via la théorie classique des invariants des formes binaires ; une
courbe hyperelliptique de genre g étant simplement reliée à une forme
binaire de degré 2g+2. La description et la construction effective de
ces algèbres d'invariants en caractéristique nulle ont débuté dans la
seconde moitié du XIXème siècle, donnant d'ailleurs naissance aux
prémices de l'algèbre commutative, et culminé en 1967 avec le résultat
de Shioda concernant les octiques (qualifié de "tour de force" par
Mumford !). En revanche, le cas des petites caractéristiques positives
reste largement ouvert, notamment pour les octiques. Ainsi, après avoir
donné un aperçu de la théorie classique, j'exposerai les résultats
actuels concernant les algèbres de formes octiques en petites
caractéristiques positives.
Vendredi 8 février 2013, exceptionnellement à 11h30
Alexei Tsygvintsev (UMPA, ENS Lyon)
Equations différentielles en biologie : du Lotka-Volterra à
Kirschnter et Panetta
En 1986 Kirschner et Panetta ont proposé un modèle mathématique
pour
décrire comment le système immunitaire contrôle le développement
de
cancer.
Nous discutons les applications et prévisions basées sur ce modèle et
montrons comment le phénomène de réapparition instantanée du
cancer,
qui échappe au système immunitaire, peut être analysé.
En modélisation nous utilisons le système de 3 équations
différentielles avec paramètres. Pour analyser les diverses questions
de stabilité, d'existence des variétés invariantes etc il est
nécessaire d'appliquer le calcul formel vu la complexité du problème.
Références
1. A. Tsygvintsev, D. Kirschner, S. Marino, A mathematical model of
Gene Therapy for the Treatment of Cancer , in the book
"Mathematical
Models and Methods in Biomedicine", Springer Verlag, berlin, 2012
2. D. Kirschner, A. Tsygvintsev. On the global dynamics of a model for
tumor immunotherapy, Journal of Mathematical Biosciences and
Engineering, Volume 6(3), pp 573-583, 2009
Vendredi 15 mars 2013
Antonia Wachter-Zeh (Ulm University & IRMAR)
Bounds on list decoding rank metric codes.
Gabidulin codes can be seen as the analogs of Reed–Solomon
(RS) codes in rank metric. There are several efficient decoding
algorithms up to half the minimum rank distance. However, in contrast
to RS codes, there is no polynomial-time list decoding algorithm; it is
not even known, whether such an algorithm can exist or not. An
exponential lower bound on the number of codewords in a ball of radius
τ around the received word would prohibit polynomial-time list decoding
since the list size can be exponential, whereas a polynomial upper
bound would show that it might be possible.
We provide bounds on the list size of rank metric codes in order to
understand whether polynomial-time list decoding is possible or not.
Three bounds on the list size are proven.
The first is a lower exponential bound for Gabidulin codes and shows
that for Gabidulin codes no polynomial-time list decoding beyond the
Johnson radius exists.
Second, an exponential upper bound is derived, which holds for any rank
metric code of length n and minimum rank distance d.
The third bound proves that there exists a rank metric code such that
the list size is exponential in the length for any radius greater than
half the minimum distance.
This implies that there cannot exist a polynomial upper bound depending
only on n and d as the Johnson bound for Hamming metric. All three
bounds reveal significant differences to codes in Hamming metric.
Vendredi 22 mars 2013
Alexander Zeh (Ulm University & LIX)
Minorer la distance minimale d'un code cyclique par intégration dans un
code produit.
A cyclic code is associated with another cyclic code to bound its
minimum distance by considering the corresponding (cyclic) product
code. The algebraic relation between these two codes allows the
formulation of syndromes and a key equation.
We outline the decoding approach for the case of errors and erasures
and show how the Extended Euclidean Algorithm can be used for decoding.
Vendredi 29 mars 2013
Thierry Combot (IMCCE)
Algorithmes pour la non-intégrabilité
Soit V une fonction rationnelle en deux variables, homogène de
degré k et avec des paramètres a. Nous présentons un algorithme
construisant une liste de conditions polynomiales sur a nécessaires
pour l'intégrabilité du système dynamique associé au potentiel V.
Lorsque ces conditions sont satisfaites, le potentiel V satisfait au
moins toutes les contraintes d'intégrabilité de Morales-Ramis-Simo à
l'ordre 2 au voisinage de toutes les orbites homothétiques, sauf
éventuellement dans un cas particulier avec k pair. On applique cet
algorithme sur des exemples déjà traités, permettant de reproduire et
de corriger certains résultats, et d'aller plus loin dans le cas V
polynomial.
Travail en collaboration avec Alin Bostan et Mohab Safey-El-Din.
Vendredi 31 mai 2013
Gwezheneg Robert (IRMAR)
Métrique rang et codes de Gabidulin en caractéristique zéro.
Après avoir introduit les $theta$-polynômes et précisé
plusieurs de leurs propriétés (notamment le lien entre leur degré et la
dimension de l'espace des racines, ainsi que la construction d'un
$theta$-polynôme s'annulant sur un espace donné), je donnerai 4
définitions de métrique "rang". Nous verrons qu'il n'y a en fait que
deux métriques distinctes, et que celles-ci sont en fait identiques
sous une hypothèse raisonnable. Enfin, nous verrons comment généraliser
les codes de Gabidulin (codes correcteurs sur des corps finis et en
métrique rang) à des corps de caractéristique nulle, ainsi qu'un
algorithme de décodage qui reste valable.
Vendredi 7 juin 2013
Laureano Gonzalez-Vega (Universidad de Cantabria, Spain)
Polynomial Algebra By Values
We will show how to work with univariate polynomials known
only by values and whose coefficients are not going to be interpolated.
Several formulae for the resultant will be presented together with
their application to problems coming from Computer Aided Geometric
Design (intersection determination, topology computation, offsets
manipulation, etc.).
Vendredi 14 juin 2013
Primitivo B. Acosta-Humánez (Universidad del Norte, Colombia), joint
work with Erwin Suazo
Liouvillian Propagators, Riccati Equation and Differential Galois Theory
In this talk a Galoisian approach to build propagators
through Riccati equations is presented. The main result corresponds to
the relationship between the Galois integrability of the linear
Schr\"odinger equation and the virtual solvability of the differential
Galois group of its associated characteristic equation. As an
application we find the propagator for a generalized harmonic
oscillator that has applications describing the process of degenerate
parametric amplification in quantum optics and the description the
light propagation in a nonlinear anisotropic waveguide.