Octobre 2008 Vendredi 17 octobre Richard Leroy (IRMAR) Certificats de positivité et minimisation polynomiale dans la base de Bernstein multivariée (résumé). 20-24 octobre : Journées nationales de calcul formel, au CIRM Décembre 2008 Vendredi 5 décembre, à 14 heures, soutenance de thèse Richard Leroy (IRMAR) Certificats de positivité et minimisation polynomiale dans la base de Bernstein multivariée. Résumé : L'étude des polynômes réels en plusieurs variables est un problème classique en géométrie algébrique réelle et en calcul formel. Plusieurs questions sont naturelles : positivité éventuelle, calcul du minimum... Nous nous proposons, dans cette thèse, d'étudier ces questions dans le cas particulier où l'étude est menée sur un simplexe de R^k (k >= 1). L'outil essentiel dans notre travail est la base de Bernstein, plus adaptée à la situation que la traditionnelle base des monômes. Elle jouit notamment de propriétés de positivité et d'encadrement essentiels à notre étude. Elle permet tout d'abord d'obtenir un algorithme décidant si un polynôme f est positif sur un simplexe V, et le cas échéant, fournissant une écriture de f rendant triviale cette positivité : on parle de certificat de positivité. En outre, elle est à l'origine d'un algorithme de minimisation polynomiale sur un simplexe. Ces deux algorithmes sont certifiés, et l'étude de leur complexité est menée dans cette thèse. Ils ont également fait l'objet d'implémentation sur ordinateur. Lundi 8 décembre, séance exceptionnelle à 10 h 30 en salle 006 Dima Pasechnik (Nanyang Technological University, Singapore) Representations of semidefinite program algebras and bounds for combinatorial optimisation problems. Abstract: Linear optimisation over the intersection of the cone of positive semidefinite matrices with an affine subspace, usually called semidefinite programming (SDP), provides an important modeling tool in combinatortial optimisation, optimal control, etc. The matrix data of the SDP generates a subalgebra of the full matrix algebra, and its representations can be used to solve the SDP more efficiently---a far-reaching generalisation of the approach pioneered by Delsarte's work on bounds for codes. We discuss recent applications of this technique to various combinatorial problems, such as lower bounds for crossing numbers of complete graphs, upper bounds on codes (e.g. permutation codes), approximation schemes for  TSP, etc. Janvier 2009 Vendredi 9 janvier Lionel Chaussade (IRMAR) Codes correcteurs sur des anneaux de Öre multivariés. Résumé : Je présenterai une généralisation des codes tordus obtenue en utilisant des anneaux de polynômes non commutatifs à plusieurs variables. Une étude des idéaux et notamment des idéaux bilatères grâce à l'utilisation de bases de Gröbner permettra de construire des codes correcteurs dont on pourra en particulier obtenir facilement la matrice génératrice sous forme standard. Vendredi 23 janvier Michael Eisermann (Grenoble) Le théorème fondamental de l'algèbre rendu effectif: une preuve réelle algébrique par les suites de Sturm Résumé: Le célèbre théorème de Sturm (1829/35) établit un algorithme élégant pour compter puis localiser les racines réelles de tout polynôme réel dans un intervalle donné. Il est peu connu que Cauchy (1831/37) l'étendit à une méthode algébrique pour compter puis localiser les racines complexes de tout polynôme complexe dans un rectangle donné. Je présente une démonstration réelle algébrique de ce beau résultat, partant des axiomes d'un corps réels clos (sans faire appel à l'analyse). Formalisant ainsi l'argument géométrique de Gauss (1799), nous obtenons une preuve réelle algébrique du théorème de Gauss-d'Alembert, alias théorème fondamental de l'algèbre, affirmant que tout polynôme complexe de degré n admet n racines complexes.  La démonstration est élémentaire dans le sens qu'elle n'utilise que le théorème des valeurs intermédiaires et l'arithmétique des polynômes réels, et elle est donc valable sur tout corps réel clos.  La démonstration est constructive dans le sens qu'elle nous fournit un algorithme explicite pour localiser les racines de tout polynôme.  L'algorithme est assez efficace pour les polynômes de degré modéré, mais dans l'état actuel il reste moins efficace que l'algorithme presque optimal de Schönhage (1982). Vendredi 30 janvier Alin Bostan (INRIA Rocquencourt) The full counting function of Gessel walks is algebraic. Résumé : The aim of the talk is to show how a difficult combinatorial problem has been recently solved using an experimental-mathematics approach combined with (rather involved) computer algebra techniques. More precisely, let $f(n,i,j)$ denote the number of lattice walks in the quarter plane which start at the origin, end at the point $(i,j)$, and consist of $n$ unit steps going either west, south-west, east, or north-east. In the early nineties, Ira Gessel conjectured that the sequence of excursions $f(n,0,0)$ is holonomic. We will present the computer-driven discovery and proof of the following generalization, obtained in August 2008 together with Manuel Kauers: the full generating series F(t,x,y) = sum_{i,j,n >= 0} f(n,i,j) x^i y^j t^n is an algebraic function. Février 2009 Vendredi 27 février, reporté Ronan Quarez (IRMAR) Représentations déterminantales des polynômes réels. Résumé: En utilisant la théorie des fonctions rationnelles non commutatives, Helton, Mccullough et Vinnikov ont établit que tout polynôme multivarié à coefficients réels peut s'écrire comme le déterminant d'une matrice symétrique réelle dont les coefficients sont des formes linéaires affines. Nous donnons une autre démonstration de ce résultat, en ne faisant appel qu'à des outils d'algèbre linéaire. Dans un second temps, nous verrons comment, dans le cas d'une seule variable, les représentations déterminantales tridiagonales symétriques des polynômes réels permettent de localiser leurs racines réelles. Nous ferons alors le lien avec les algorithmes de Sturm et de Sylvester. Mars 2009 Vendredi 6 mars, reporté David Lubicz (IRMAR) Une généralisation due à Mumford de la théorie des fonctions thêta. Résumé: Dans cet exposé, on présentera les bases de la théorie des fonctions thêta algébriques développée dans les 60 par Mumford. Cette théorie est un pendant arithmétique de la théorie classique due à Riemann. Une chose intéressante est le caractère effectif de la théorie de Mumford qui permet de représenter par des systèmes d'équations homogènes les variétés abéliennes ainsi que leurs espaces de modules. Vendredi 27 mars Pierre-Vincent Koseleff (IMJ) Construction de noeuds toriques et recherche exhaustive de noeuds de Chebyshev à deux ponts. Avril 2009 Vendredi 10 Avril Eric Schost (Western Ontario) Cartes routières sur les hypersurfaces lisses et compactes. Vendredi 24 avril Ainhoa Aparicia Monforte (Xlim) Une notion de "forme réduite" pour les systèmes linéaires différentiels et intégrabilité de systèmes hamiltoniens. Résumé: Un système hamiltonien à n degrés de liberté est dit intégrable s'il possède n intégrales premières fonctionellement indépendantes et en involution. Le théorème de Morales-Ramis affirme que si un système hamiltonien est intégrable en ce sens alors son équation variationelle $Y'=AY$ avec $A\in\mathfrak{sp}(2n,k)$ satisfait que $Lie(Y'=AY)$ est abélienne.  Dans cet exposé nous introduisons la notion de "forme réduite" ( intuitivement la forme la plus creuse que peut prendre un système différentiel linéaire) et  nous donnons un algorithme qui soit met $A\in\mathfrak{sp}(4,k)$ sous forme réduite si $Lie(Y'=AY)$, soit nous dit que $Lie(Y'=AY)$ n'est pas abélienne. Cet algorithme appliqué dans le contexte du théorème de Morales-Ramis nous permet soit de dire que le système hamiltonien de départ est non intégrable soit à préparer le système variationel à l'application du théorème de Morales-Ramis-Simó. L'ensemble sera illustré par des exemples. Ceci est un travail développé en collaboration avec mon directeur de thèse Jacques Arthur Weil (XLIM DMI  Université de Limoges). Juin 2009 Mercredi 3 juin, 10h30, salle 4 Daouda Diatta (Xlim & INRIA Sophia Antipolis) Topologie d'une surface algébrique implicite. Résumé: Etant donnée une surface algébrique implicite nous nous intéressons au problème de la construction d'un complexe simplicial qui lui est isotope. Nous montrerons qu'il est possible de construire un tel complexe à partir du calcul de la topologie de la "silhouette" de la surface. Nous nous sommes inspirés des travaux de Gonzalez Véga et El Kahoui pour construire un algorithme  certifié basé sur les propriétés des polynômes sous-résultants et une analyse des fibres singulières de la "silhouette" de la surface. L'algorithme que nous présenterons a été implémenté en Mathémagix . Vendredi 12 juin Christophe Chabot (Xlim & INRIA Rocquencourt) Codes quasi-cycliques sur des anneaux de matrices. Résumé : Nous nous intéressons ici à la généralisation de résultats connus sur les suites récurrentes linéaires classiques aux suites récurrentes linéaires ayant un polynôme caractéristique à coefficients matriciels. Nous montrerons qu'il est possible de construire des codes quasi-cycliques à partir de telles suites (par analogie avec la construction de codes cycliques à partir de suites récurrentes linéaires classiques). Nous obtiendrons alors la notion de code quasi-cyclique annulé par un polynôme à coefficients matriciels. Finalement nous construirons des codes quasi-cycliques auto-duaux Euclidiens et Hermitiens qui dans la plupart des cas atteignent les bornes connues pour les distances minimales. Vendredi 19 juin Colas Bardavid (IRMAR) Torseurs en théorie de Picard-Vessiot : l'approche de Ledet-Juan Résumé : Cet exposé est destiné à préparer la visite d'Arne Ledet (Texas Tech University), qui sera à Rennes du 2 au 17 juillet. J'expliquerai, d'après les travaux d'Arnet Ledet et Lourdes Juan, comment les torseurs interviennent en théorie de Galois différentielle linéaire et comment on peut les utiliser pour produire des équations différentielles génériques dont le groupe de Galois est prescrit. Mardi 23 juin, 9h, salle 16 Mohab Safey (Universite Pierre et Marie Curie) Computing roadmaps in a smooth compact algebraic hypersurface. Jeudi 25 juin, 10h30, salle 4 Saugata Basu (Perdue University) Polynomial hierarchy, Betti numbers and a real analogue of Toda's theorem. Juillet 2009 Mercredi 8 juillet, 11h30, salle 16 Arne Ledet (Texas Tech University, Lubbock) Describing differential Galois extensions.