Jéxposerai un algorithme pour determiner la topologie d'une courbe plane dans une boite donnee. La technique employee est par subdivision et repose sur l'analyse des points singuliers au moyen du degre topologique.

Reference: "Visualisation of implicit algebraic curves", http://hal.inria.fr/inria-00175062

An nxn matrix A is rank structured if its submatrices strictly contained in the lower/upper triangular part have "small" rank with respect to n. Most part of companion-like matrices are rank structured. In this talk we present some recent results concerning rank-structured matrices, like semi-separable and quasi-separable matrices, and apply them to the design of effective algorithms for computing the eigenvalues of companion-like matrices. In particular, we show that the matrix sequence generated by the QR iteration maintains the rank structure for most companion-like matrices. This fact is used to design an implementation of the QR algorithm which requires O(n) arithmetic operations per step instead of O(n2). We discuss about using these properties for the design of a new polynomial rootfinding software.

Linear systems with structures such as Toeplitz-, Vandermonde- or Cauchy-likeness can be solved in O~(alpha^2 n) operations, where n is the matrix size, alpha is its displacement rank, and O~ denotes the omission of logarithmic factors. We show that for Toeplitz-like and Vandermonde-like matrices, this cost can be reduced to O~(alpha^{omega-1} n), where omega is a feasible exponent for matrix multiplication over the base field. The best known estimate for omega is omega < 2.38, resulting in costs of order O~(alpha^{1.38} n). We also present consequences for Hermite-Padé approximation and bivariate interpolation.

Surface implicitization, i.e. finding the implicit equation of an algebraic surface defined parametrically, is a classical problem and there are numerous approaches to its solution. In this talk, we will show that the linear syzygies of the parametrization of a rational surface can be used to represent and to compute its implicit equation under suitable conditions. This is, in some sense, a natural generalization of the well-known method of "moving curves" for plane curve implicitization.

In Computer Aided Geometric Design (CAGD), the parameterized surfaces are used delimiting volumes. The computation of the intersection curve between such two surfaces is thus crucial for the description of the CAGD objects. An often used method to address this problem consist in using a mesh for each surface, and then to proceed to their intersection (intersection of triangles). Other methods for the intersection problem deal with global representations of the surfaces such as B-splines, however the usual CAGD procedures (offsetting, drafting, ...) do not conserve this model and procedural surfaces that are based on approximations are required. So, even if the intersection methods are exact, they only provide an approximation of the "real" intersection curve. This can be of bad quality, because the approximations of the surfaces are separated from the intersection process and are somehow "global''. In the general case, the only informations that we can access for a parameterized surface are "local" (its evaluation). Thus, a general algorithm is a sampling algorithm like the mesh representation. If we use shapes more complex than the triangles, then the quality of the surfaces approximation will be better and thus the intersection locus too. For example, we can use Bézier surface patches of small degree. But if we want to use this kind of representation, we have to intersect efficiently such two polynomial prameterized surfaces. In this talk, we deal with this problem. This work presents a subdivision method in order to compute the topology of a four dimension implicit curve. This approach is efficient and avoid some drawbacks that appear in projection methods which are used by many authors.

La decomposition (uni-multivarié) d'un polynome f est son écriture (si elle existe) sous la forme f=u(h) où u est un polynome univarié de degré supérieur à 2 et h un polynome multivarié. Ce type de décomposition est un cas particulier de la factorisation absolue de f. Récemment de nouveaux résultats effectifs ont été obtenus pour la factorisation absolue des polynomes (théorème de Noether, Bertini, Ostrowski, factorisation approchée). Ces résultats découlent du travail de W. Ruppert qui a montré comment lier la factorisation absolue avec la résolution d'une e.d.p.. Ici, nous verrons comment obtenir le meme type de resultats pour la decomposition à l'aide dé.d.p. provenant du jacobien. Nous verrons donc comment obtenir les equations de la variété algébrique des polynomes decomposables, comment ramener l'étude d'un polynome de n à 2 variables, comment se comportent les polynomes indecomposables modulo p, et comment faire de la decomposition approchée.

Le calcul du plus petit commun multiple de plus de deux opérateurs linéaires, différentiels ou à différences, intervient dans des problèmes comme léxtraction de sous-séries de séries multi-sommables, en théorie de la resommation, ou pour la sommation symbolique de fonctions rationnelles. Dans cet exposé, nous nous intéressons aux calculs en bonne complexité de multiples communs d'opérateurs à coefficients polynomiaux. Il apparaît tout d'abord que le calcul de p.p.c.m. itérés est une mauvaise approche. Nous développons une reformulation linéaire du problème donnant une borne précise sur le degré des coefficients du p.p.c.m. en fonction des degrés des entrées. Cette borne permet l'analyse de plusieurs algorithmes, existant ou nouveau, pour le calcul du p.p.c.m. Une meilleure complexité est obtenue en relâchant la contrainte de minimalité du p.p.c.m. : une autre formulation linéaire montre qu'il existe des multiples communs de taille bien moindre que celle du p.p.c.m. En en calculant deux en bonne complexité, puis en en prenant un p.g.c.d., on obtient un bon algorithme pour le calcul du p.p.c.m.

(Travail en cours avec A. Bostan, Z. Li et B. Salvy.)

This is a joint work with Martin Sombra. By applying a refinement of the Bernstein-Kusnirenko bound, we recover a "tropical" result, which is that the Newton polygon of the implicit equation of a rational plane curve is explicitly determined by the multiplicities of any of its parametrizations. As an application, we determine the Newton polygon of a curve parameterized by generic Laurent polynomials or by generic rational functions, with explicit genericity conditions. We also study the variety of rational curves with given Newton polygon, and show in particular that any convex lattice polygon with positive area is the Newton polygon of a rational plane curve.

On s'intéresse à des méthodes de continuation pour la résolution d'un système d'équations polynomiales qui sont construites non pas par relèvement dans la variété d'incidence du problème d'un segment dans léspace des systèmes mais à partir des géodésiques dans cette variété d'incidence pour une métrique associée au conditionnement.

Nous donnons un algorithme certifié qui calcul un objet linéaire par morceaux qui est isotope à l'intersection de deux surfaces en intersection complète.

Dans cet exposé, je présenterai un nouvel algorithme de calcul de la décomposition primaire d'un idéal de polynomes zero-dimensionel. Le cout de cet algorithme est polynomial en le nombre de variables, le cout d'évaluation des équations, et le nombre de Bézout du système considéré.

Une méthode présentée dans Numerical Recipes pour l'intégration par la méthode de Gauss-Legendre n'a été prouvée que récemment. Nous montrons comment cette méthode se prête à une algorithmique rapide par des techniques d'évaluation-multipoints à base de multiplication rapide. Il s'agit d'un travail en cours en collaboration avec Bruno Salvy.

A geometric approach is presented for designing algorithms to factor bivariate approximate polynomials over C[x,y]. Given a perturbed composite polynomial, stably square-free, satisfying a genericity hypothesis : to be the product of random polynomials, an algorithm is described which construct a nearby composite polynomial and its irreducible factors.

Whether algebraic or differential, one can distinguish two families of applications for invariants of group actions: equivalence problems and symmetry reduction. Both applications raise the initial computational issue: given a group action, can we compute a generating set of invariants and determine their syzygies, i.e. the relationships the generating set satisfies.

In this talk I shall concentrate on the struture of the ring of differential invariants, elaborating on Fels and Olver's interpretation of Cartan's moving frame. The original results are: - a finite and complete set of syzygies for the normalized invariants. - the generation property of Maurer-Cartan invariants. They support some of the functionalities of the Maple package AIDA (Algerbaic Invariants and their Differential Algebra) that I'm developing. This latter has been applied to exhibit new result in conformal and projective geometry.

Dans cet exposé, je considérerai la classe des systèmes d'EDP linéaires complètement intégrables de la forme dY = (A(x,y)/x^p dx + B(x,y)/y^q dy) Y où (p,q) est un couple déntiers naturels non nuls, A et B sont des matrices de taille m dont les coefficients sont des séries formelles en x et y à coefficients complexes.

Hélène Charrière a montré dans sa thèse que modulo quelques transformations non constructives, les solutions locales en (x,y) = (0,0) de tels systèmes s'obtiennent en combinant les solutions locales en 0 de deux systèmes différentiels linéaires singuliers en 0 : l'un en u, gouvernant le comportement en x, l'autre en v, gouvernant celui en y.

Je présenterai un début de réponse pour le calcul des solutions formelles locales en (0,0) de tels systèmes. En employant un algorithme permettant de "réduire" le couple (p,q), on peut distinguer les cas réguliers et irréguliers. Jéxpliquerai dans le cas régulier comment calculer après "réduction" les solutions locales formelles en 0 en rendant effectif un théorème de Gérard et Levelt. Je terminerai léxposé en pointant les difficultés pour calculer les solutions locales formelles dans le cas irrégulier une fois le couple (p,q) réduit et les possibles généralisations à la dimension supérieur a 2.

In this talk we will present new faster absolute factorization algorithms for bivariate polynomials in small positive characteristic.

Etant donné un polynôme F in k[x,y] et une racine c du dicriminant de F en y, il est difficile de calculer numériquement les développements de Puiseux de f au dessus de c (i.e. les séries en (x-c) solutions de f vu comme un polynôme univarié en y). Le calcul symbolique de ces séries peut s'avérer couteux, que ce soit par léxtension de k dans laquelle sont définies les coefficients ou par la croissance de la taille de ces coefficients. De plus, l'évaluation de ces coefficients peut demander une précision non négligeable, de notamment à cette croissance des coefficients.

Néanmoins, si une boite noire fournissait les données exactes nécessaires pour effectuer ce calcul, il serait alors possible de calculer numériquement ces séries en suivant au fur et à mesure des calculs les indications données par la boite noire. Les informations exactes dont on a besoin sont de deux types : les pentes successives des polygones de Newton et les multiplicités des racines des polynômes caractéristiques associés.

Nous détaillerons un algorithme qui calcule numériquement ces développements de Puiseux, en utilisant comme "boite noire" le calcul modulo un nombre premier p bien choisi de ces développements de Puiseux. Le nombre premier p est tel que tous les termes qui introduisent une séparation des racines de f (cést à dire les termes provenant d'une pente non entière ou ceux provenant d'un polynôme caractéristique ayant plus d'une racine) ne soient pas réduit à 0 modulo p. A partir de ces séries calculées modulo p, on reconstruit la suite des polygones et multiplicités dont on a besoin pour nos calculs numériques. Puis cet "arbre de polygones" nous permet de calculer numériquement les séries.

Cést un travail en collaboration avec Marc Rybowicz

Nous montrerons comment l'utilisation conjointe de la théorie des modules et de l'algèbre homologique permet de donner des conditions générales pour qu'une matrice R d'opérateurs fonctionnels (e.g., opérateurs différentiels, de retards, de décalage) soit algébriquement équivalente à une matrice bloc-triangulaire ou bloc-diagonale S (i.e., tel qu'il existe des matrices unimodulaires U et V vérifiant que S=V , R , U^{-1} soit une matrice bloc-triangulaire ou bloc-diagonale). Pour cela, nous montrerons comment calculer l'anneau des endomorphismes d'un module intrinsèquement à la matrice R et comment l'étude de ses projecteurs combinée à certains résultats d'algèbre (théorèmes de Quillen-Suslin et de Stafford) permettent de factoriser ou décomposer certains systèmes fonctionnels linéaires. Finalement, nous illustrerons ces différents résultats sur des exemples venant de la physique mathématique et de l'automatique à l'aide du package Morphisms.

On montre que la plupart des opérations classiques peuvent se faire pour des polynômes exprimés dans la base de Chebychev avec la même complexité asymptôtique que s'ils étaient exprimés dans la base des puissances. On donnera aussi quelques résultats sur des formulations matricielles du résultats quand les polynômes sont exprimés dans la base de Chebychev. Si certains résultats donnés ici étaient connus de Barnett, d'autres semblent originaux (des extension de la formule dite de Barnett).

It is classical that univariate algebraic functions satisfy linear differential equations with polynomial coefficients. Linear recurrences follow for the coefficients of their power series expansions. We show that the linear differential equation of minimal order has coefficients whose degree is cubic in the degree of the function. We also show that there exists a linear differential equation of order linear in the degree whose coefficients are only of quadratic degree. Furthermore, we prove the existence of recurrences of order and degree close to optimal. We study the complexity of computing these differential equations and recurrences. We deduce a fast algorithm for the expansion of algebraic series.

Families of orthogonal polynomials satisfy recurrence relations which are often the key to the design of fast algorithms. In this talk, we consider conversion problems, from an orthogonal basis to the monomial basis and conversely. Using the recurrence relation on orthogonal polynomials, one easily comes up with efficient algorithms for the direct conversion. We give here a fast algorithm for the converse direction, exploiting classical continued fractions identities and algorithm transposition techniques.

In 1994 Boo Barkee and others have written a paper Why you cannot even hope to use Gr"obner Bases in Public Key Cryptography: an open letter to a scientist who failed and a challenge to those who have not yet failed. Since 1994, further attempts have been made, that gave rise to several cryptosystems now known as Polly Cracker systems. None of these proposals have been successful, and while Gr"obner Bases are now an established tool for cryptoanalysis, the challenge of Boo Barkee still stands w.r.t. the design point of view. We outline a description on how all these attempts have failed.

The analysis shows that the only possibility of a successful Polly Cracker can be one with binomial ideals, toric ideals in particular. But the correspondence of toric ideals with lattices brings the possibility of redefining some known lattice cryptosystems as Polly Cracker systems; whether this will result in breaking these cryptosystems, (those that still stand) or if the introduction of Gr"obner basis methods will result in stronger lattice cryptosystems is too early to say. We will in particular discuss some experiences on the cooperation of Gr"obner basis methods (Buchberger algorithm) and lattice methods (LLL algorithm) to solve toric ideals/lattices.

Avec un automorphisme theta non trivial de Fq on définit via la règle Xa = theta(a)X (avec a in Fq) une structure d'anneau non commutatif sur

Soit A un anneau differentiel effectif de series formelles calculables dans K[[z_1, ..., z_k]] pour un corps K, et supposons que l'on dispose d'un teste de nullite effectif dans A. Considerons un systeme déquations differentielles algebriques P_1 (f) = ... = P_p (f) = 0 avec P_1, ..., P_p dans A{F}. Si f dans K[[z_1, ..., z_k]] est la solution unique de ce systeme, en supposant des conditions initiales adequates, alors léxtension de A par f fournit un nouvel anneau differentiel effectif A{f}. Sous une hypothese supplementaire legere, on donnera un teste de nullite pour les elements de A{f}.

Soit V une sous-variété de C^n, F : V->C^m (n>=m) une application analytique complexe et Sigma(F) son lieu singulier c'est à dire l'ensemble des points z pour lesquels DF(z) n'est pas surjective. Le champ de Newton associé à F est défini par N_F(z)=-DF(z)^\dag F(z). Supposons qu'il existe un potentiel de Lyapunov f(z) pour lequel les sous-ensembles { z in V : f(z) <= lambda } pour lambda<=lambda0 sont compacts. Dans ce cas, à partir d'un temps T>0 les trajectoires du champ de Newton sont elles-même contenues dans un compact. Question : quels sont les points limites de ces trajectoires? Nous distinguerons essentiellement deux cas : les applications F à singularités génériques et les autres.

On utilise des critères d'interpolation algébrique dans des variétés toriques pour retrouver et améliorer un algorithme de factorisation polynomiale initialement développé (dans le cas dense) par Chèze-Galligo-Rupprecht. Grossomodo, le gain déffectivité est proportionnel au nombre de facettes du polytope de Newton.

Un couple de polynômes (f_0,g_0) d'une variable étant donné, on décrit un algorithme de calcul de la distance de (f_0,g_0) à la variété résultante.