Séminaire Calcul Formel 
Responsable : Thomas Cluzeau
Horaires : Jeudi 10h30
Lieu : Salle XR 203 du bâtiment XLIM,
Faculté des Sciences et Techniques,
123 avenue Albert Thomas, 87060 Limoges
Orateur : Alexandre Benoit (Univ. Paris 6, INRIA)
Titre : Séries de Fourier généralisées solutions d'équations différentielles
Résumé : Les polynômes de Tchebychev, de Hermite ou autres polynômes orthogonaux classiques, les fonctions de Bessel et certaines autres familles de fonctions spéciales, forment des
bases d'espaces hilbertiens adaptés. Il est donc utile de pouvoir développer des fonctions sur ces bases, et ces développements s'appellent des séries de Fourier généralisées. Les séries de Taylor sont
un cas particulier (base monomiale), mais aussi les séries de Tchebychev ou de Neuman (base des fonctions de Bessel).
Quand une telle série est solution d'une équation différentielle linéaire à coefficients polynomiaux, ses coefficients eux-mêmes satisfont une récurrence linéaire à coefficients polynomiaux. Dans ce
travail nous interprétons cette équation comme le numérateur d'une fraction d'opérateurs de récurrence. Cette interprétation nous permet de donner un algorithme général pour calculer de telles
récurrences et fournit une vision simple des algorithmes existants pour plusieurs familles de fonctions spécifiques.
Avril 2012 :
Orateur : Fabien Monfreda (Univ. Toulouse)
Titre : Méthode de réduction de l'indice d'équations différentielles algébriques quasilinéaires par déflation
Résumé : cliquez ici
Orateur : Paola Boito (Université de Limoges ; CNRS ; XLIM DMI)
Titre : Introduction aux matrices quasiséparables et calcul rapide de valeurs propres.
Orateur : Catherine Stenger (Univ. La Rochelle)
Titre : Sur une construction de séries formelles définissant des fonctions holomorphes pour des équations différentielles partielles.
Mars 2012 :
Orateur : Sergei A. Abramov (Computing Centre of the Russian Academy of Sciences)
Titre : On linear differential systems with power series coefficients
Février 2012 :
Orateur : Moulay Barkatou (XLIM - DMI)
Titre : Sur les parties exponentielles d'un système différentiel linéaire à coefficients méromorphes.
Janvier 2012 :
Orateur : Pierre-Vincent Koseleff (UPMC Paris 6 & INRIA - OURAGAN)
Titre : Noeuds et courbes de Chebyshev
Orateur : Meisam Sharify (CMAP, École polytechnique)
Titre : Bounds for the eigenvalues of a matrix polynomial by using Tropical algebra and application to the numerical computation of eigenvalues
Décembre 2011 :
Orateur : Flavia Stan (INRIA Rocquencourt, Centre INRIA-Microsoft Research)
Titre : A symbolic summation approach to Feynman integral calculus
Orateur : Sergei A. Abramov (Computing Centre of the Russian Academy of Sciences)
Titre : On polynomial solutions of linear partial differential and (q-)difference equations.
Résumé : The question whether a given linear partial differential, difference or $q$-difference equation with polynomial coefficients has non-zero polynomial solutions or not, is -- in general -- undecidable.
However, if a differential or difference equation $L(y)=0$, $y = y(x_1,\ldots,x_m)$, $m>1$, with constant coefficients has a non-zero polynomial solution then $L(1)=0$, and if $L(1)=0$ then the equation
has polynomial solutions of all degrees. For a given non-negative integer $d$, all solutions of degree $d$ of such an equation can be found by, e.g., the method of undetermined coefficients.
The space of polynomial solutions of a given $q$-difference equation with constant coefficients can be described algorithmically, and this space may be of finite or infinite dimension.
The results presented in this talk were obtained by the author jointly with M.Petkovsek.
Novembre 2011 :
Orateur : Carole El Bacha (Université de Limoges ; CNRS XLIM UMR 6172 - DMI)
Titre : Méthodes algébriques pour la résolution d'équations différentielles matricielles d'ordre arbitraire
Octobre 2011 :
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Juin 2011 :
Mars 2011 :
Février 2011 :
Cette réduction consiste simplement en le calcul d'une transformation monomiale inversible qui rend un polynôme dont la taille dense est du même ordre de grandeur
que la taille du polygone de Newton du polynôme donné en entrée. En particulier, si la complexité d'un algorithme de factorisation de polynôme à deux variables
s'exprime en le produit des degrés partiels, notre résultat permet de dire que cette même complexité est en fait en la taille du polygone de Newton du polynôme considéré.
systèmes carrés c'est-à-dire le cas où il y a autant d'équations que de fonctions inconnues. Cependant, les systèmes apparaissants dans certaines applications
comme la théorie du contrôle sont en général rectangulaires et non carrés.
Dans cet exposé, en utilisant une approche via l'analyse algébrique constructive, je montrerai comment on peut réduire l'intégration d'un système différentiel
linéaire rectangulaire à celle d'un système différentiel linéaire carré. Cette méthode est implantée en Maple en utilisant la librairie OreModules.
Ceci est un travail en collaboration avec M. Barkatou (XLIM-DMI), C. El Bacha (XLIM-DMI) et A. Quadrat (INRIA Saclay - Projet DISCO).
Janvier 2011 :
Orateur : Paola Boito (XLIM-DMI)
Titre : Bornes pour fonctions de matrices et applications aux méthodes de calcul de structures électroniques.
Résumé : Linear scaling methods, used in quantum chemistry and solid state physics for computation of electronic structures, rely on the phenomenon of localization:
for certain choices of the basis functions, the Hamiltonian matrix that describes a physical system is banded or sparse. The associated density matrix, which is a function
of the Hamiltonian, is expected to exhibit an off-diagonal decay behavior, which may allow to replace the matrix with a banded approximation.
Our goal is to give a rigorous mathematical description and proof of this property. By means of polynomial approximation and matrix analysis techniques, we formulate
asymptotic bounds on the entries of the density matrix (as well as more general matrix functions). Such results allow to bound the error due to sparse/banded approximation.
Applications of bounds for matrix functions are not limited to computational physics. The talk will present examples of how our approach can be used to estimate matrix functions
that describe the connectivity properties of networks.
This is joint work with Michele Benzi and Nader Razouk.
Novembre 2010 :
Dans une première partie, je rappellerai brièvement la notion de forme réduite pour un système différentiel linéaire.
Ensuite, je montrerais en détail une application aux équations variationelles provenant de systèmes dynamiques : quand une équation variationelle est sous forme
réduite et que son algèbre de Lie est abélienne (tout ceci sera expliqué dans l'exposé), nous proposons un procédé pour mettre sous forme réduite l'équation variationelle
suivante. Nous en déduisons (partiellement) une forme effective du fameux critère de non-intégrabilité de Morales-Ramis-Simo pour les systèmes hamiltoniens.
Tout ceci sera illustré sur un ou deux exemples.
Octobre 2010 :
Titre : Équations variationelles d'ordre supérieur et reconstruction d'intégrales premières formelles d'un champ de vecteurs complexe.
Résumé : Soit X un champ de vecteurs complexe et soit x une solution non ponctuelle de X. Nous inspirant des travaux de Morales-Ramis et Simo,
nous donnons une méthode qui permet de construire des intégrales premières formelles de X en termes de solutions rationelles des équations variationelles le long de x.
Nous montrons que les intégrales premières formelles de X sont, contre toute attente, caractérisées par une famille de relations purement linéaires.
Grâce à ces relations linéaires nous arrivons à réduire partiellement les équations variationelles et à encadrer le nombre des intégrales premières holomorphes du système étudié.
Ceci est utile notamment pour l'étude de l'intégrabilité des systèmes Hamiltoniens.
Orateur : Adrien Poteaux (LIP6)
Titre : Opérations modulo un ensemble triangulaire en un temps quasi linéaire.
Résumé : cliquez ici
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Avril 2010 :
Mars 2010 :
Janvier 2010 :
Horaires : Jeudi 10h30
Lieu : Salle XR 203 du bâtiment XLIM,
Faculté des Sciences et Techniques,
123 avenue Albert Thomas, 87060 Limoges
PROGRAMME
Mai 2012 : - Jeudi 31 mai à 10h30
Orateur : Alexandre Benoit (Univ. Paris 6, INRIA)
Titre : Séries de Fourier généralisées solutions d'équations différentielles
Résumé : Les polynômes de Tchebychev, de Hermite ou autres polynômes orthogonaux classiques, les fonctions de Bessel et certaines autres familles de fonctions spéciales, forment des
bases d'espaces hilbertiens adaptés. Il est donc utile de pouvoir développer des fonctions sur ces bases, et ces développements s'appellent des séries de Fourier généralisées. Les séries de Taylor sont
un cas particulier (base monomiale), mais aussi les séries de Tchebychev ou de Neuman (base des fonctions de Bessel).
Quand une telle série est solution d'une équation différentielle linéaire à coefficients polynomiaux, ses coefficients eux-mêmes satisfont une récurrence linéaire à coefficients polynomiaux. Dans ce
travail nous interprétons cette équation comme le numérateur d'une fraction d'opérateurs de récurrence. Cette interprétation nous permet de donner un algorithme général pour calculer de telles
récurrences et fournit une vision simple des algorithmes existants pour plusieurs familles de fonctions spécifiques.
Avril 2012 :
- Jeudi 19 avril à 10h30
Orateur : Fabien Monfreda (Univ. Toulouse)
Titre : Méthode de réduction de l'indice d'équations différentielles algébriques quasilinéaires par déflation
Résumé : cliquez ici
Orateur : Paola Boito (Université de Limoges ; CNRS ; XLIM DMI)
Titre : Introduction aux matrices quasiséparables et calcul rapide de valeurs propres.
- Jeudi 5 avril à 10h30
Orateur : Catherine Stenger (Univ. La Rochelle)
Titre : Sur une construction de séries formelles définissant des fonctions holomorphes pour des équations différentielles partielles.
Résumé : On construit des solutions formelles
d'équations aux dérivées partielles
linéaires comme combinaisons linéaires de puissances de
solutions d'équations différentielles
du premier ordre non linéaires, en suivant le cadre de la méthode tanh. On donne des conditions suffisantes sous lesquelles ces séries formelles définissent des fonctions
holomorphes sur certains polydisques épointés de $C^2$. De plus, on étudie la vitesse de croissance de ces solutions au voisinage de leurs points singuliers.
du premier ordre non linéaires, en suivant le cadre de la méthode tanh. On donne des conditions suffisantes sous lesquelles ces séries formelles définissent des fonctions
holomorphes sur certains polydisques épointés de $C^2$. De plus, on étudie la vitesse de croissance de ces solutions au voisinage de leurs points singuliers.
Mars 2012 :
- Jeudi 29 mars à 10h30
Orateur : Sergei A. Abramov (Computing Centre of the Russian Academy of Sciences)
Titre : On linear differential systems with power series coefficients
Résumé : Given an arbitrary-order linear
differential system with formal power series coefficients, we want to
decide whether the system has non-zero Laurent series solutions.
We suppose that the series coefficients of systems are represented algorithmically, and this implies that the question under consideration is undecidable in general.
However it is decidable in the case when we know in advance that a given system is of full rank (a joint work with M.Barkatou and D.Khmelnov).
We suppose that the series coefficients of systems are represented algorithmically, and this implies that the question under consideration is undecidable in general.
However it is decidable in the case when we know in advance that a given system is of full rank (a joint work with M.Barkatou and D.Khmelnov).
Février 2012 :
- Jeudi 2 février à 10h30 (REPORTÉ - CF FELIM 2012)
Orateur : Moulay Barkatou (XLIM - DMI)
Titre : Sur les parties exponentielles d'un système différentiel linéaire à coefficients méromorphes.
Résumé : Étant donné un
système différentiel linéaire $\frac{dY}{dx}= A(x)
Y$ de dimension $n$ à coefficients méromorphes
d'ordre $p$ à l'origine, nous montrons que les
parties exponentielles
du système et les parties principales des développements de Puiseux à l'origine des valeurs propres de $A(x)$ coïncident toujours jusqu'à un certain ordre que nous donnons explicitement en
fonction de $n$ et de $p$. De ce premier résultat, nous déduisons d'autres résultats plus fins et mieux exploitables pour le calcul effectif des parties exponentielles du système de départ.
du système et les parties principales des développements de Puiseux à l'origine des valeurs propres de $A(x)$ coïncident toujours jusqu'à un certain ordre que nous donnons explicitement en
fonction de $n$ et de $p$. De ce premier résultat, nous déduisons d'autres résultats plus fins et mieux exploitables pour le calcul effectif des parties exponentielles du système de départ.
Janvier 2012 :
- Jeudi 26 janvier à 10h30
Orateur : Pierre-Vincent Koseleff (UPMC Paris 6 & INRIA - OURAGAN)
Titre : Noeuds et courbes de Chebyshev
Résumé : cliquer ici
- Jeudi 19 janvier à 10h30
Orateur : Meisam Sharify (CMAP, École polytechnique)
Titre : Bounds for the eigenvalues of a matrix polynomial by using Tropical algebra and application to the numerical computation of eigenvalues
Résumé : cliquer ici
Décembre 2011 :
- Jeudi 8 décembre à 10h30
Orateur : Flavia Stan (INRIA Rocquencourt, Centre INRIA-Microsoft Research)
Titre : A symbolic summation approach to Feynman integral calculus
Résumé : We discuss two methods based on Wilf-Zeilberger
summation motivated by the computation of Feynman parameter integrals.
For the first method, the integrals are rewritten as multisums of hypergeometric terms to fit the input class of WZ-summation. These summation problems are highly nested sums with
non-standard boundary conditions. They satisfy inhomogeneous recurrences containing sums of lower nested depth on the right-hand sides.
Another approach to evaluate Feynman integrals is by representing them as nested Mellin-Barnes integrals. We show how WZ-methods determine recurrences for contour integrals of this type,
thus eliminating the need to find sum representations.
For the first method, the integrals are rewritten as multisums of hypergeometric terms to fit the input class of WZ-summation. These summation problems are highly nested sums with
non-standard boundary conditions. They satisfy inhomogeneous recurrences containing sums of lower nested depth on the right-hand sides.
Another approach to evaluate Feynman integrals is by representing them as nested Mellin-Barnes integrals. We show how WZ-methods determine recurrences for contour integrals of this type,
thus eliminating the need to find sum representations.
- Jeudi 1 décembre à 10h30
Orateur : Sergei A. Abramov (Computing Centre of the Russian Academy of Sciences)
Titre : On polynomial solutions of linear partial differential and (q-)difference equations.
Résumé : The question whether a given linear partial differential, difference or $q$-difference equation with polynomial coefficients has non-zero polynomial solutions or not, is -- in general -- undecidable.
However, if a differential or difference equation $L(y)=0$, $y = y(x_1,\ldots,x_m)$, $m>1$, with constant coefficients has a non-zero polynomial solution then $L(1)=0$, and if $L(1)=0$ then the equation
has polynomial solutions of all degrees. For a given non-negative integer $d$, all solutions of degree $d$ of such an equation can be found by, e.g., the method of undetermined coefficients.
The space of polynomial solutions of a given $q$-difference equation with constant coefficients can be described algorithmically, and this space may be of finite or infinite dimension.
The results presented in this talk were obtained by the author jointly with M.Petkovsek.
Novembre 2011 :
- Jeudi 10 novembre à 10h30
Orateur : Carole El Bacha (Université de Limoges ; CNRS XLIM UMR 6172 - DMI)
Titre : Méthodes algébriques pour la résolution d'équations différentielles matricielles d'ordre arbitraire
Résumé : Dans cette thèse, nous développons
de nouvelles méthodes algébriques
pour la résolution d’une classe importante de
systèmes d’équations
différentielles linéaires d’ordre arbitraire.
De tels systèmes ont des applications dans de nombreuses disciplines scientifiques comme la chimie, la physique, la mécanique et la théorie du contrôle. Dans un premier temps, nous nous
intéressons à l’analyse locale des systèmes d’équations différentielles linéaires ordinaires au voisinage d’une singularité. Nous développons des algorithmes pour le calcul des solutions
régulières formelles. Ces algorithmes sont directs, i.e., ne transforment pas le système en un autre du premier ordre et de taille plus grande. Nos approches sont fondées sur l'utilisation des propriétés
des matrices polynomiales dont le déterminant joue le même rôle que les polynômes indiciels dans le cas scalaire. Puis, nous nous intéressons à l'étude des formes k-simples d’un système différentiel
linéaire explicite du premier ordre. Ces formes donnent des informations sur les pentes entières du polygone de Newton du système et permettent de calculer les solutions formelles sans ramification.
Notre contribution se reflète par le développement d’une méthode directe pour le calcul de ces formes. Dans un second temps, nous étudions les systèmes d’équations algébro-différentielles linéaires
composés d’équations différentielles ordinaires couplées à des équations algébriques et nous proposons des algorithmes afin de les découpler en une partie purement différentielle et une autre purement
algébrique. Une autre contribution de la thèse est l'étude des complexités et l'implémentation en Maple des algorithmes mis en oeuvre.
De tels systèmes ont des applications dans de nombreuses disciplines scientifiques comme la chimie, la physique, la mécanique et la théorie du contrôle. Dans un premier temps, nous nous
intéressons à l’analyse locale des systèmes d’équations différentielles linéaires ordinaires au voisinage d’une singularité. Nous développons des algorithmes pour le calcul des solutions
régulières formelles. Ces algorithmes sont directs, i.e., ne transforment pas le système en un autre du premier ordre et de taille plus grande. Nos approches sont fondées sur l'utilisation des propriétés
des matrices polynomiales dont le déterminant joue le même rôle que les polynômes indiciels dans le cas scalaire. Puis, nous nous intéressons à l'étude des formes k-simples d’un système différentiel
linéaire explicite du premier ordre. Ces formes donnent des informations sur les pentes entières du polygone de Newton du système et permettent de calculer les solutions formelles sans ramification.
Notre contribution se reflète par le développement d’une méthode directe pour le calcul de ces formes. Dans un second temps, nous étudions les systèmes d’équations algébro-différentielles linéaires
composés d’équations différentielles ordinaires couplées à des équations algébriques et nous proposons des algorithmes afin de les découpler en une partie purement différentielle et une autre purement
algébrique. Une autre contribution de la thèse est l'étude des complexités et l'implémentation en Maple des algorithmes mis en oeuvre.
- Jeudi 3 novembre à 10h30
Orateur : Esteban Segura Ugalde (Université de Limoges ; CNRS XLIM UMR 6172 - DMI)
Titre : Polynomial Root-finding via Structured Matrices
Abstract: We study the problem of approximating the zeros of an univariate polynomial (up to machine precision). Some popular iterative root-finding methods construct companion matrices (Frobenius, Lagrange) associated with the given polynomial and use eigensolvers to find the eigenvalues of such matrices. Our goal is to study this root-finding technique, exploiting the structure (e.g., diagonal plus rank one) of companion matrices to obtain a decrease of computational cost and memory requirements.
Octobre 2011 :
- Jeudi 13 octobre à 10h30
Orateur : Aurélien Greuet (Université de Versailles et Équipe SALSA/INRIA/LIP6/UPMC)
Titre : Utilisation des variétés polaires pour la résolution de problèmes d'optimisation.
Résumé : On considère des problèmes d'optimisation globale algébrique : il s'agit de calculer la borne inférieure f* d'un polynôme f à plusieurs variables sous des contraintes polynomiales. Résoudre un tel problème peut avoir plusieurs significations selon le contexte applicatif.
On peut chercher à obtenir un codage algébrique (polynôme à une variable et intervalle d'isolation) afin d'éviter les problèmes d'approximations. On peut aussi, à l'aide de décompositions en sommes de carrés de polynômes, chercher à obtenir des bornes inférieures certifiées sur f*. Enfin, dans plusieurs applications, en particulier pour l'utilisation
du calcul numérique, il est intéressant de savoir si f* est atteint ou pas.
Dans cet exposé, on s'intéresse aux propriétés des variétés polaires, définies comme lieux critiques de projections sur des sous-espaces linéaires. Leurs propriétés sont utiles pour résoudre les problèmes précédents. Dans un premier temps, nous les utiliserons pour l'optimisation sous des contraintes polynomiales. Nous verrons comment améliorer le calcul numérique de décomposition en sommes de carrés, puis comment obtenir un algorithme de calcul formel pour calculer f*.
Dans un second temps, nous verrons comment utiliser les variétés polaires pour décider, dans le cas non contraint, si f* est atteint.
Certains de ces travaux sont communs avec M. Safey El Din; d'autres sont communs avec F. Guo, M. Safey El Din et L. Zhi.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Juin 2011 :
- Jeudi 30 juin à 10h30
Orateur : Clemens Raab (Linz, Autriche)
Titre : Symbolic Integration in Differential Fields
Résumé : We give an overview of an extension of Risch's algorithm for finding elementary integrals. This extension is applicable to a certain
class of Liouvillian and non-Liouvillian functions. Some subproblems related to solving differential equations will be outlined. Examples of
indefinite and definite integrals will be given as well.
Mars 2011 :
- Jeudi 31 mars à 11h
Orateur : Paola Boito (Université de Limoges ; CNRS ; XLIM DMI)
Titre : Matrice compagnon généralisée et calcul du pgcd approché
Résumé : We study a variant of the univariate approximate polynomial GCD problem, where the coefficients of one polynomial $f(x)$ are known exactly, whereas the
coefficients of the second polynomial $g(x)$ may be perturbed. Our approach relies on the properties of the matrix which describes the operator of
multiplication by $g$ in the quotient ring $\mathbb{C}[x]/(f)$. In particular, the structure of the null space of the multiplication matrix
contains all the essential information about GCD(f,g). Moreover, the multiplication matrix exhibits a displacement structure that allows us to
design a fast algorithm for approximate GCD computation with quadratic complexity w.r.t. polynomial degrees.
- Jeudi 10 mars à 10h30
Orateur : Andy Novocin (ENS-Lyon)
Titre : Practical Polynomial Factoring in Polynomial Time
Résumé : This talk presents some recent and on-going work on factoring polynomials in Z[x]. The goal of this work is to arrive at a practical, implementable,
and efficient algorithm for which we can prove a tight complexity bound (which should be the best existing complexity bound). We give the overall structure of
our algorithm with insights into the practical and theoretical issues which guide the design. We also present the behavior of the algorithm in theory and give some
early running times of our implementation.
Février 2011 :
- Jeudi 24 février à 10h30
Orateur : Jérémy Berthomieu (LIX, École polytechnique)
Titre : Factorisation de polynômes à deux variables convexe-denses.
Cette réduction consiste simplement en le calcul d'une transformation monomiale inversible qui rend un polynôme dont la taille dense est du même ordre de grandeur
que la taille du polygone de Newton du polynôme donné en entrée. En particulier, si la complexité d'un algorithme de factorisation de polynôme à deux variables
s'exprime en le produit des degrés partiels, notre résultat permet de dire que cette même complexité est en fait en la taille du polygone de Newton du polynôme considéré.
- Jeudi 17 février à 10h30
Orateur : Abdelkarim Chakhar (XLIM-DMI)
Titre : Analyse algébrique et algèbre différentielle pour l'étude de systèmes différentiels quasilinéaires.
Résumé : Les méthodes de l'analyse algébrique (D-modules et algèbre homologique) permettent d'étudier de façon systématique les systèmes linéaires d'équations aux
dérivées partielles.
Il n'existent pas de théorie similaire pour les systèmes d'équations aux dérivées partielles non linéaires.
Dans cet exposé, je montrerai comment on peut, en travaillant sur des anneaux différentiels, se servir de l'analyse algébrique constructive pour déduire certaines
propriétés (e.g. symétries, lois de conservations, etc) sur une classe particulières d'équations non linéaires, dites quasi-linéaires.
- Jeudi 3 février à 10h30
Orateur : Thomas Cluzeau (XLIM-DMI)
Titre : Analyse algébrique constructive et intégration de systèmes différentiels rectangulaires.
systèmes carrés c'est-à-dire le cas où il y a autant d'équations que de fonctions inconnues. Cependant, les systèmes apparaissants dans certaines applications
comme la théorie du contrôle sont en général rectangulaires et non carrés.
Dans cet exposé, en utilisant une approche via l'analyse algébrique constructive, je montrerai comment on peut réduire l'intégration d'un système différentiel
linéaire rectangulaire à celle d'un système différentiel linéaire carré. Cette méthode est implantée en Maple en utilisant la librairie OreModules.
Ceci est un travail en collaboration avec M. Barkatou (XLIM-DMI), C. El Bacha (XLIM-DMI) et A. Quadrat (INRIA Saclay - Projet DISCO).
Janvier 2011 :
- Jeudi 20 janvier à 10h30
Orateur : Paola Boito (XLIM-DMI)
Titre : Bornes pour fonctions de matrices et applications aux méthodes de calcul de structures électroniques.
Résumé : Linear scaling methods, used in quantum chemistry and solid state physics for computation of electronic structures, rely on the phenomenon of localization:
for certain choices of the basis functions, the Hamiltonian matrix that describes a physical system is banded or sparse. The associated density matrix, which is a function
of the Hamiltonian, is expected to exhibit an off-diagonal decay behavior, which may allow to replace the matrix with a banded approximation.
Our goal is to give a rigorous mathematical description and proof of this property. By means of polynomial approximation and matrix analysis techniques, we formulate
asymptotic bounds on the entries of the density matrix (as well as more general matrix functions). Such results allow to bound the error due to sparse/banded approximation.
Applications of bounds for matrix functions are not limited to computational physics. The talk will present examples of how our approach can be used to estimate matrix functions
that describe the connectivity properties of networks.
This is joint work with Michele Benzi and Nader Razouk.
Novembre 2010 :
- Jeudi 18 novembre à 10h30
Orateur : Jacques-Arthur Weil (XLIM-DMI)
Titre : Formes réduites pour les équations variationelles de systèmes différentiels.
Dans une première partie, je rappellerai brièvement la notion de forme réduite pour un système différentiel linéaire.
Ensuite, je montrerais en détail une application aux équations variationelles provenant de systèmes dynamiques : quand une équation variationelle est sous forme
réduite et que son algèbre de Lie est abélienne (tout ceci sera expliqué dans l'exposé), nous proposons un procédé pour mettre sous forme réduite l'équation variationelle
suivante. Nous en déduisons (partiellement) une forme effective du fameux critère de non-intégrabilité de Morales-Ramis-Simo pour les systèmes hamiltoniens.
Tout ceci sera illustré sur un ou deux exemples.
- Jeudi 4 novembre à 10h30
Orateur : Mioara Joldes (ENS-Lyon)
Titre : Tools for Rigorous Computing using Chebyshev Series Approximations
Résumé : Performing numerical computations, yet being able to provide rigorous mathematical statements about the obtained result, is required in many domains
like global optimization, ODE solving or integration. Taylor models are a widely used rigorous computation tool: they associate to a function a pair made of a
Taylor approximation polynomial and a rigorous remainder bound. This approach benefits from the advantages of numerical methods, but also gives the ability
to make reliable statements about the approximated function. A natural idea is to try to replace Taylor polynomials with better approximations such as minimax
approximation, Chebyshev truncated series or interpolation polynomials. Despite their features, an analogous to Taylor models, based on such polynomials,
has not been yet well-established in the field of validated numerics.
In this talk we propose two approaches for computing such models : one is based on interpolation polynomials at Chebyshev nodes; the other on using Chebyshev
truncated series.We compare the quality of the obtained remainders and the performance of the approaches to the ones provided by Taylor models.
We also present two practical examples where this tool can be used: supremum norm computation of approximation errors and rigorous quadrature.
This talk is based on a joint work with Nicolas Brisebarre.
Octobre 2010 :
- Jeudi 21 octobre à 10h30
Orateur : Olivier Ruatta (Université de Limoges, XLIM-DMI)
Titre : Champ de Weierstrass (Durand-Kerner-Dochev and co).
Résumé : Lors d'un épisode précédent (séminaire d'équipe puis JNCF), j'ai expliqué qu'il n'existe pas d'automate rationnel BCSS (c'est-à-dire dans le modèle de calcul Blum-Cucker-Shub-Smale) permettant d'approximer une racine d'un polynôme pour presque tout point de départ et presque tout polynôme dès que le degré des polynômes considérés dépasse strictement 4. Je me suis servi de se fait pour motiver l'inérêt pour la conjecture de Weierstrass : si on ne peut pas en approximer une racine, on peut les approximer toutes avec l'itération de Weierstrass qui donne un automate rationnel. C'est toujours une conjecture.
Je me suis beaucoup intéressé à cette conjecture et pour étudier la dynamique de cette itération discrète, j'ai introduit le champ de vecteurs de Weierstrass. C'est un champs de vecteur dont les points fixes sont génériquement isolés et ont les racines du polynôme d'entrée pour coordonnées. J'en ai déduit un automate globalement convergent pour calculer toutes les racines d'un polynôme de degré plus grand ou égale à 5.
J'ai passé sous le tapis beaucoup de propriétés géométriques de ce champ de vecteurs. Et beaucoup de questions qui peuvent motiver des intégrateur d'EDO ! Réparont cette forfaiture.
Dans cette exposé, je monterai la construction de ce champ de vecteurs et j'en étudierai quelques propriétés fondamentales (c'est un remonté d'un champ radial sur un revêtement différentiel adéquat ...). Je montrerai quelques expériences avec ce champ de vecteurs (quelques portraits de phase) et je donnerai quelques problèmes auquels je ne sais pas répondre sur les intégrales premières de ce champ (l'algébricité d'icelles). Cela pourrais s'appeler la longue route vers Galois si ce n'était déjà pris.
- Jeudi 14 octobre à 11h
Orateur : Guillaume Chèze (Université de Toulouse)
Titre : À propos du calcul des polynômes de Darboux.
Résumé : Durant cet exposé nous allons considérer des équations différentielles de la forme: dX/dt= A(X,Y), dY/dt= B(X,Y), où A,B \in Z[X,Y], deg A \leq d,
deg B \leq d, et la hauteur de A et B est majorée par H. De nombreuses propriétés de telles équations sont liées aux polynômes de Darboux de la
dérivation correspondante: D = A(X,Y) \partial_X + B(X,Y) \partial_Y. Les polynômes de Darboux sont habituellement calculés avec la méthode des
coefficients indéterminés. Avec cette méthode nous devons résoudre un système polynomial. Nous allons montrer que cette méthode peut conduire au
calcul d'un nombre exponentiel de polynômes de Darboux réductibles. On présentera ensuite une méthode permettant de calculer tous les polynômes
de Darboux irréductibles de degré inférieur à N avec une complexité binaire polynomiale en d, log(H) et N.
- Jeudi 23 septembre à 10h30
Titre : Équations variationelles d'ordre supérieur et reconstruction d'intégrales premières formelles d'un champ de vecteurs complexe.
Résumé : Soit X un champ de vecteurs complexe et soit x une solution non ponctuelle de X. Nous inspirant des travaux de Morales-Ramis et Simo,
nous donnons une méthode qui permet de construire des intégrales premières formelles de X en termes de solutions rationelles des équations variationelles le long de x.
Nous montrons que les intégrales premières formelles de X sont, contre toute attente, caractérisées par une famille de relations purement linéaires.
Grâce à ces relations linéaires nous arrivons à réduire partiellement les équations variationelles et à encadrer le nombre des intégrales premières holomorphes du système étudié.
Ceci est utile notamment pour l'étude de l'intégrabilité des systèmes Hamiltoniens.
- Jeudi 16 septembre à 10h30
Orateur : Adrien Poteaux (LIP6)
Titre : Opérations modulo un ensemble triangulaire en un temps quasi linéaire.
Résumé : cliquez ici
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Avril 2010 :
- Jeudi 29 avril à 14h
Orateur : Luca de Feo (LIX, École polytechnique)
Titre : Fast Arithmetics in Artin Schreier Towers
Résumé : Soit K un corps de caractéristique p, une extension d'Artin-Schreier est une extension de corps engendrée par un polynome de la forme X^p - X - a.
Toute extension séparable de degrée p peut être exprimée comme une extension d'Artin-Schreier, en particulier toute extension de degré p sur un corps fini.
Les tours d'Artin-Schreier apparaissent naturellement en théorie des nombres, par exemple dans le calcul des points de p-torsion d'une variété
abélienne. On présente ici des algorithmes asymptotiquement rapides pour les opérations arithmetiques de base dans les tours d'Artin-Schreier et
pour certaines operations avancées tel le calcul du morphisme de frobenius ou des traces.
Mars 2010 :
- Mercredi 31 mars à 16h30
Orateur : Eleonora Guerrini (Université de Grenoble)
Titre : Codes systématiques et idéaux polynomiaux.
Résumé : Dans cet exposé un modèle algébrique pour la caractérisation des codes correcteurs systématiques est présenté.
L'intérêt pour cette famille dérive de la volonté de généraliser les codes linéaires afin de rechercher des codes qui soient optimaux du point de vue de la distance.
En fait, il est possible démontrer que tout code linéaire est équivalent à un code systématique, mais il existe des codes systématiques non-linéaires à distance plus grande
de tout linéaire qui partage les même paramètres n (longueur) k (dimension). A la base de cette approche, le fait que tout code systématique est en correspondance avec la
base de Groebner réduite de son idéal d'annulation. Grâce à cette correspondance, nous décrivons un algorithme qui, étant donnés n,k, d entiers, fournit la caractérisations
des codes systématiques avec paramètres n,k et distance au moins d.
Le point central de l'algorithme est le calcul de la base de Groebner d'un certain idéal B(n,k,t) qui est invariant sous l'action d'un groupe de permutations et présente de
propriétés d'inclusions dans d'autres idéaux du même type (par ex. dans B(n+1,k,t+1) et B(n+1,k+1,t)).
Avec des techniques similaires, il est possible aussi de formuler un algorithme pour le calcul de la distribution des distances d'un code systématique et une nouvelle borne
pour la distance de ces codes.
- Jeudi 18 mars à 14h
Orateur : Valéry Mahé (Université de Framche-Comté)
Titre : Calculer les termes des suites elliptiques à divisibilité.
Résumé : Les suites elliptiques à divisibilité sont des suites d'entiers issues de la théorie des courbes elliptiques dont les facteurs premiers ont des applications au dixième
problème de Hilbert : un anneau A étant donné, existe t il un algorithme décidant en un temps fini si un polynôme sur A en n variables a un zéro défini sur A.
Une conjecture de primalité affirme que les suites elliptiques à divisibilité n'ont qu'un nombre fini de termes premiers. Pour l'instant cette conjecture n'est prouvée
que sous une hypothèse dite de magnification.
Dans cet exposé nous expliquerons comment calculer l'ensemble des termes premiers des suites elliptiques à divisibilité magnifiées en utilisant des résultats d'approximation diophantienne.
- Mercredi 17 mars à 16h30
Orateur : Alain Couvreur (INRIA Saclay, Projet TANK & LIX, École Polytechnique)
Titre : Calcul des paramètres de l'orthogonal d'un code géométrique.
Résumé : Introduits par Goppa au début des années 80, les codes géométriques on connu un succès spectaculaire dans les dernières
décennies. Ce domaine de recherche a entre autres l'intérêt de connecter les domaines de mathématiques à priori éloignés que sont l'arithmétique et
la géométrie algébrique d'un côté et la théorie de l'information de l'autre.
Dans cet exposé, nous présenterons les rudiments de la théorie des codes géométriques sur les courbes. Dans un second temps, nous aborderons le cas
- moins exploré - de la dimension supérieure et présenterons des méthodes d'estimation des paramètres de codes sur des surfaces et de leurs orthogonaux.
- Jeudi 4 mars à 14h
Orateur : Xiaoli Wu
Title: Determining Singular Solutions of Polynomial Systems via Symbolic-Numeric Reduction to Geometric Involutive Form
Abstract: We present a method based on symbolic-numeric reduction to geometric involutive form to compute the primary component and the differential
operators for an isolated singular solution of a polynomial ideal. The singular solution can be exact or approximate. If the singular solution is known with
limited accuracy, then we propose a quadratic-convergent method to refine it to high accuracy.
Janvier 2010 :
- Jeudi 28 à 14h
Orateur : José Cano (Université de Valladolid - Espagne)
Titre : L'espace des solutions formelles d'une équation différentielle ordinaire.
Résumé : La méthode classique du Polygone de Newton permet de construire pour tout entier k un ensemble semi-algébrique
dans lequel se trouvent toutes les troncations à k termes des séries formelles solutions d'une équations différentielle ordinaire donnée.
On montrera que la dimension de cet ensemble semi-algébrique est bornée par l'ordre de l'équation différentielle.