# Séminaire de Calcul Formel SALSA

Le séminaire de du projet INRIA/LIP6 SALSA a lieu environ toutes les deux semaines le vendredi après-midi. Il se tient dans les locaux du LIP6, 104 avenue du Président Kennedy, Paris 16e (pour les personnes extérieures au LIP6 veuillez vous munir d'une pièce d'identité pour le contrôle de sécurité à l'entrée).

Les sujets abordés lors de ces séminaires sont majoritairement orientés vers les aspects algébriques du calcul scientifique. Ils s'intéressent aussi aux interfaces entre le calcul symbolique et numérique ainsi qu'aux aspects logiciels et applicatifs du calcul formel comme la cryptologie et la robotique par exemple.

Organisateur : Guénaël Renault (si vous voulez faire partie de la liste de diffusion envoyez moi un email).

Vendredi 12 décembre à 11h00, Salle 847 Hoon Hong (North Carolina State University)

### Root Bound for Pham Systems

Root bound plays an important role in isolating and approximating the roots of polynomial equations, analyzing their computational complexity, etc.

In this talk, we briefly review root bounds for one univariate polynomial and multivariate polynomial system. Then, we describe a root bound for Pham systems, which are certain nice'' multivariate polynomial systems. We show that the root bound is much tighter than the one for arbitrary multivariate polynomial system.

We hope that the tighter bound would be useful for obtaining faster algorithms for isolating and approximating the roots of Pham system.
Mercredi 17 décembre à 11h00, Salle 550 Tetsuo Ida, (Symb. Comp. Research Lab. Univ. of Tsukuba, Japan)

### Geometric Computing and Reasoning for Origami - Eos approach

In this talk I give an overview of our Eos (e-origami system) project. Recently Eos has been extended to allow for more user-friendly construction of and more powerful reasoning about computational origami. As for the former, we developed a front end for Eos for origamists interested in computational origami. Eos is running at a server side, and is accessed with standard web browsers. The front end, called WebEos, is entirely developed using GWT (Google Web Toolkit, hence written in Java) and it allows a smooth interaction with user's web browser and back end Eos. While most computationally intensive task is carried out at the back end, WebEos provides rich means for interaction with Eos.

As for the latter, we implemented a small first-order language for specifying the construction of origami to extend, in expressive power as a language, the so-called Huzita's axioms, and incorporated it into Eos. We noted that Huzita's axiomatic definition of basic fold operations is the statement about the constructibility of origami by specifying a method of operation. Huzita's axioms can be easily described as the first-order statement about the constructibility of new fold lines using the existing lines and points of concern. The construction can be viewed as generating numbers by regarding the coordinates of the intersections as pairs of numbers. It is well known that the constructible numbers by Huzita's axioms form a field that contains the subfield consisting of the numbers constructible with compass and straightedge. Therefore, one can conclude that origami is more powerful than compass and straightedge.

Eos provides a geometrical language by which we can reason about the constructibility, executes the construction described in that language and realizes the origami construction as if we folded the origami by hands, with more powerful methods. We further discuss a number of features that we needed for reasoning origami construction including the step-wise polynomial generation during the construction, theorem proving by Grobner bases method, and origami graph generation.
Vendredi 27 février à 14h00, Salle 550 Luca De Feo, (École Polytechnique)

### Arithmétique rapide dans les Tours d'Artin-Schreier

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.

Cette étude, en collaboration avec E.Schost de l'University of Western Ontario, a fait l'objet d'exposés à C4 et au CMS Winter Meeting et d'un papier soumis à ISSAC 09.
Vendredi 13 mars à 14h00, Salle 550 Mohab Safey El Din, (Equipe-projet SALSA - INRIA/LIP6 - UPMC)

### Complexity issues for the computation of roadmaps in real algebraic sets

Travail en collaboration avec E. Schost de l'University of Western Ontario,

We consider the problem of constructing roadmaps of real algebraic sets. The problem was introduced by Canny to answer connectivity questions and solve motion planning problems. Given $s$ polynomial equations with rational coefficients, of degree $D$ in $n$ variables, Canny's algorithm has a Monte Carlo cost of $s^n\log(s) D^{O(n^2)}$ operations in $\mathbb{Q}$; a deterministic version runs in time $s^n \log(s) D^{O(n^4)}$. The next improvement was due to Basu, Pollack and Roy, with an algorithm of deterministic cost $s^{d+1} D^{O(n^2)}$ for the more general problem of computing roadmaps of semi-algebraic sets ($d \le n$ is the dimension of an associated object).

We give a Monte Carlo algorithm of complexity $(nD)^{O(n^{1.5})}$ for the problem of computing a roadmap of a compact hypersurface $V$ of degree $D$ in $n$ variables; we also have to assume that $V$ has a finite number of singular points. Even under these extra assumptions, no previous algorithm featured a cost better than $D^{O(n^2)}$.
Vendredi 27 mars à 14h00, Salle 550 Daouda Niang Diatta (Université de Limoges-XLIM)

### Topologie de l'Intersection de deux Surfaces Algébriques et Maillages Isotopiques d'une Surface Implicite.

Les algorithmes que nous présenterons sont symboliques-numériques, certifiés et fortement basés sur les propriétés des sous résultants. Le premier, permet de calculer la topologie de la courbe d'intersection de deux surfaces algébriques implicites. Le deuxième fournit le maillage isotopique d'une surface algébrique singulière.
Et pour finir nous parlerons de quelques résultats sur un travail en cours sur le calcul de la topologie de l'intersection de deux surfaces paramétrées.
Vendredi 27 mars à 15h00, Salle 550 Rong XIAO (Equipe-projet SALSA INRIA/LIP6)

### On Using Triangular Decomposition for Solving Parametric Systems

Joint work with Fabrice ROUILLIER

We will show that triangular decomposition can be used to compute effectively discriminant variety (DV) for general parametric polynomial systems. The link between DV (or some components of DV) and classical subsets naturally provided by triangular structure is studied first. Then an algorithmic frame based on triangular decomposition was proposed for DV computation. Finally some optimizations of the general frame are suggested and tested.
Lundi 27 avril à 13h00, Salle 548 Ting Zhao (Equipe-projet SALSA INRIA/LIP6)

### Real Root Formula for Polynomial Equations with Constraints

Joint work with Hoon Hong (North Carolina State University, USA) and Dongming Wang (Equipe-projet SALSA INRIA/LIP6 - CNRS, UPMC France & Beihang University, China)

We present the real-root formula for the general polynomial equation of low degree (less than 5), the nontrivial case. The formula provides a symmetric representation in which the real roots of the equation are separated, allows one to verify directly when the equation has real roots, and is suitable for efficient numerical computation. The representations of the real roots coupled with real constraints are achieved by combining Thom's lemma and the complex-root formula. The need of such formula for efficiently solving dynamic geometric constraints involving inequalities is the main motivation for this work.
Vendredi 29 mai à 14h00, Salle 548 Alin Bostan (Projet Algorithms, INRIA Paris-Rocquencourt)

### The full counting function of Gessel walks is algebraic

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 \geq 0} f(n,i,j) x^i y^j t^n$ is an algebraic function.
Vendredi 12 juin à 13h30, Salle 548 Pierre-Vincent Koseleff (UPMC et EPI-Salsa)

### Les premiers neouds rationnels de Chebyshev.

Travail commun avec D. Pecker (UPMC) et F. Rouillier (EPI-Salsa).

Un noeud de Chebyshev C(a,b,c,x) est un noeud qui admet la paramétrisation polynomiale x(t)=T_a(t); y(t)=T_b(t) ; z(t)= T_c(t + x), où a et b sont des entiers premiers entre-eux, c est un entier et x un réel et T_n est le polynôme de Chebyshev de degré n.

Tout noeud non compact peut-être obtenu comme noeud polynomial (Vassiliev). Nous avons montré dans que tout noeud est un un noeud de Chebyshev. Le but de cet exposé est de décrire explicitement les premiers noeuds rationnels de Chebyshev.
Après avoir rappelé quelques propriétés élémentaires de la théorie des noeuds, nous décrirons lez différentes étapes.
* Les noeuds rationnels sont déterminés par leur fraction de Schubert. Pour a=3 et a=4, nous allons déterminer b tel que la courbe de Chebyshev : T_a(t),T_b(t) est une projection plane du noeud. Cet algorithme est basé sur l'existence (et l'unicité) de certaines décompositions en fractions continues.
* Pour a,b,c fixés l'ensemble des x tels que C(a,b,c,x) est singulier est fini. Nous déterminons un nombre rationnel r dans chaque intervalle de son conplémentaire.
* Nous déterminons enfin la fraction de Schubert du noeud C(a,b,c,r) en évaluant la nature de chaque croisement au-dessus des points doubles de la projection. Il s'agit de déterminer les signes de nombres algébriques et nous utilisons une version hybride de l'algorithme Isolate (arithmétique flottante et entière multi-précision) de Rouillier et Zimmermann.

Nous obtenons ainsi une liste des premiers noeuds rationnels de Chebyshev.
Vendredi 12 juin à 14h30, Salle 548 David Lubicz (CELAR et IRMAR - Université de Rennes 1)

### Calcul de correspondances modulaires entre variétés abéliennes

Travail commun avec Jean-Charles Faugère et Damien Robert.

L'objet de cet exposé est de donner un équivalent en dimension plus grande que un des classiques polynômes modulaires. Nous utilisons pour cela la description de l'espace des modulaires des variétés abéliennes donnée par les thêta constantes.
Lundi 22 juin à 14h00, Salle 548 Luis Penaranda (Loria - Inria Nancy-Grand Est)

### On the topology of planar algebraic curves

We revisit the problem of computing the topology and geometry of real algebraic plane curve. The topology is of prime interest but geometric information, such as the position of singular and critical points, is also relevant. A challenge is to compute efficiently this information for the given coordinate system even if the curve is not in generic position.

Previous methods based on the cylindrical algebraic decomposition (CAD) use sub-resultant sequences and computations with polynomials with algebraic coefficients. A novelty of our approach is to replace these tools by Gröbner basis computations and isolation with rational univariate representations. This has the advantage of avoiding computations with polynomials with algebraic coefficients, even in non-generic positions. Our algorithm isolates critical points in boxes and computes a decomposition of the plane by rectangular boxes. This decomposition also induces a new approach for computing an arrangement of polylines isotopic to the input curve. We also present an analysis of the complexity of our algorithm. An implementation of our algorithm demonstrates its efficiency, in particular on high-degree non-generic curves.

Ceci est un travail conjoint avec Jinsan Cheng, Marc Pouget, Sylvain Lazard, Fabrice Rouillier et Elias Tsigaridas.

Cette page suit les consignes du W3C :