| Raphael Bomboy | Réductibilité et résolubilité des équations aux différences finies
linéaires. Le but de ce travail est de donner des algorithmes praticables de factorisation et de résolution des équations aux différences finies linéaires. Peter Hendriks et Michael Singer ont déjà donné une définition des solutions liouvilliennes d'une telle équation et un algorithme de recherche de ces solutions. Cet algorithme utilise intensément la recherche de solutions hypergéométriques de systèmes d'équations linéaires associés au moyen de l'algorithme de Petkov\v{s}ek. Ce dernier a pour inconvénient de pouvoir nécessiter de calculer dans diverses extensions du corps des coefficients apparaissants dans l'équation. Après avoir rappelé quelques généralités sur la théorie de Galois des équations aux différences finies linéaires et étudié la réductibilité d'une équation ou d'un système d'équations et son lien avec l'espace des solutions, nous introduisont, en suivant les idées déjà développées par Michael Singer pour les équations différentielles, la notion d'Eigenring d'un système. Cette notion nous permettra de donner un algorithme de factorisation d'un système d'équations aux différences finies linéaire et un algorithme de recherche des solutions liouvilliennes d'un opérateur qui se ramènent le plus possible à la recherche des solutions rationnelles à coefficients dans le corps considéré de systèmes d'équations différentielles associés. Dans certains cas, ils pourront nécessiter la recherche de solutions hypergéométriques, mais là aussi sans qu'il soit nécessaire de sortir de notre corps de base. Nous concluons par quelques exemples. |
| Manuel Bronstein | Algèbre linéaire pour matrices de polynômes de Ore On décrit un nouvel algorithme de calcul du rang d'une matrice de polynômes de Ore. Dans le cas de polynômes commutatifs, cet algorithme permet aussi de calculer déterminants et noyaux, ainsi que de dérandomiser la résolution par Hensel de Ax=b. Dans le cas de matrices de récurrences, cet algorithme permet de calculer les solutions rationelles de systèmes linéaires différentiels ou aux différences finies sans les découpler. |
| Peter Clarkson | An Introduction to Inverse Scattering
In this lecture I shall give an introduction to integrable systems and soliton theory. There are several physically significant nonlinear partial differential equations which are solvable by the inverse scattering method, which in effect reduces the solution of the nonlinear equation to that of a linear integral equation. The prototype example will be the Korteweg-de Vries equation u_t + 6 u u_x + u_{xxx} = 0. The inverse scattering method will be viewed as a Riemann-Hilbert boundary value problem. This involves complex function theory which is convenient and relevant to generalizations. The proposed outline of the lectures is as follows:
M.J. Ablowitz and P.A. Clarkson, Solitons, Nonlinear Evolution Equations and Inverse Scattering, L.M.S. Lect. Note Series, vol. 149, C.U.P. (1991) |
| Olivier Cormier | Sur les equations differentielles lineaires
d'ordre 4 et 5
Dans cet expose je donnerais les degres minimaux possibles d'une solution algebrique de l'equation de Riccati associee a une equation differentielle lineaire homogene irreductible d'ordre 4 et 5. En particulier je montre que ce degre algebrique est borne par 120 pour l'ordre 4 et 55 pour l'ordre 5. Je montrerais aussi une application interessante de la recherche de solutions liouvilliennes d'equations differentielles pour la theorie de Galois inverse classique. |
| Alicia Dickenstein |
Rational Hypergeometric Functions Multivariate hypergeometric functions associated with toric varieties were introduced by Gel'fand, Kapranov and Zelevinsky, as the solutions of a holonomic system of partial linear differential equations with polynomial coefficients constructed from an integer matrix and a complex parameter vector. Singularities of such functions are discriminants, that is, divisors projectively dual to torus orbit closures. We show that most of these potential denominators never appear in rational hypergeometric functions. We conjecture that the denominator of any rational hypergeometric function is a product of resultants, that is, a product of special discriminants arising from Cayley configurations. This conjecture is proved for toric hypersurfaces (which correspond to hypergeometric functions of a single variable) and for toric varieties of dimension at most three. Toric residues are applied to show that every toric resultant appears in the denominator of some rational hypergeometric function. This is joint work with Eduardo Cattani and Bernd Sturmfels. |
| Emmanuelle Dottax | Calcul du genre d'une courbe algebrique. Etant donnee une courbe irreductible, B. Trager a montre qu'on pouvait calculer son genre en se basant sur la formule de Hurwitz, mais en deduisant les indices de ramification des exposants de l'equation differentielle satisfaite par une solution de l'equation algebrique. Cette methode a ete implementee en Maple, mais la construction de l'equation differentielle necessite la resolution (couteuse!) d'un systeme lineaire. Nous avons donc "transporte" la methode sur un systeme differentiel du premier ordre satisfait lui aussi par les solutions algebriques, sur lequel on applique l' algorithme de [1] afin de recuperer les invariants necessaires. [1] S.Abramov et M.Bronstein, On Solutions of Linear Functional Systems, manuscript soumis à la conférence ISSAC'2001. |
| Jean-Guillaume Dumas | Forme normale de Smith entière via la Valence : expériences
avec de grandes matrices creuses d'Homologie. Nous présentons un nouvel algorithme pour calculer la forme normale de Smith de grandes matrices creuses à coefficients dans Z. Nous réduisons le problème à des calculs modulo des puissances de nombres premiers de taille de l'ordre du mot machine. Ainsi, l'algorithme permet des résolutions quand un grossissement des coefficients pénalise largement les méthodes classiques. Nous avons implémenté plusieurs variantes de cet algorithme (élimination et/ou techniques itératives par matrices en "boîtes noires"), tant séquentielles que parallèles, puisque ses performances pratiques dépendent de manière cruciale de la mémoire disponible. Notre méthode s'est avérée utile en topologie algébrique pour le calcul de groupes d'homologie de complexes simpliciaux. |
Ioannis Emiris | Matrices hybrides du résultant creux par décompositions mixtes
Étant donné un système de 3 polynômes en 2 variables, décrits par leurs polygones de Newton, nous proposons un algorithme géométrique pour construire des matrices dont le déterminant est un multiple non-nul du résultant creux. La construction de base est un relèvement des polygones en 3 dimensions, linéaire par morceaux, qui définit une décomposition mixte de la somme de Minkowski avec les propriétés desirées. Notre matrice est de type Sylvester, avec une ligne supplémentaire de type Bézout. Elle correspondent à une transformation linéaire introduite par Cattani, Dickenstein et Sturmfels [CDS98]. Cette matrice est de dimension minimale, en général, parmi les matrices de type Sylvester. Une implémentation en Maple et certains exemples en CAO sont presentés. L'extension en plusieurs dimensions est ouverte et passe par la généralisation du relèvement combinatoire. Il s'agit de travail commun avec Carlos d'Andrea, U. de Buenos Aires |
| André Galligo |
Auto-intersections de splines bicubiques En Conception Assistée par Ordinateur, une des questions encore mal résolue est la détection et le contrôle des singularités des surfaces paramétrées utilisées dans les représentation des bords des objets solides. La recherche des points où la surface se recoupe peut être particulièrement délicate. Une recherche dichotomique est confrontée à des problèmes d'échelle et de bruit. Il faut donc aussi essayer d'aborder la question en tirant parti des informations algébriques sur les représentations des surfaces considérées. Dans [2], Andersson, Peters et Stewart, par des méthodes de convexité, donnent des conditions suffisantes intéressantes qui permettent de certifier que la surface ne possède pas de point d'auto-intersection. Cependant cela reste des conditions suffisantes et cela ne permet pas de provoquer et de contrôler la présence de singularités. Nous souhaitons étudier la question de façon analytique pour des classes de surfaces simples souvent utilisées dans les applications et mettre en place de nouveaux outils de calcul robustes. Nous abordons ici le cas assez particulier, mais deja bien riche, de surfaces de Bezier bi-cubiques ayant deux familles de courbes cubiques planes. La forme normale des équations paramétrées de telles surfaces est : x = u^3 -3 u, y = v^3 -3 v, z = a1 u^3 v^3 + a2 u^3 v^2 +a 3 u^2 v^3 + a4 u^3 v + a5 u^2 v^2 + a6 u v^3 + a7 u^3 + a8 u^2 v + a9 u v^2 + a10 v^3 + a11 u^2 + a12 u v + a13 v^2. Pour ces surfaces, on peut tracer dans le plan $(u, v)$ la courbe des paramètres (u, v) correspondant aux points doubles. On verra que cette courbe est (en général) donnée par une équation de degré 36. Mais heureusement elle a plusieurs composantes réelles que l'on peut décrire et tracer succéssivement et rapidement en repérant des points spéciaux. On peut également décrire les paramètres (u, v) correspondant aux points triples. Enfin on introduit et étudie une nouvelle courbe : celle formée par les milieux des couples de paramètres (u1, v1) et (u2, v2) correspondant aux points doubles. Elle nous permet de bien décrire l'involution naturelle sur chacune des composantes réelles de la courbe des points doubles. On peut alors décrire et produire les images des différentes situations géométriques que l'on peut rencontrer avec ce modèle. Ce travail est le fruit d'un travail commun avec M. Stillman. Il apporte une contribution partielle de l'équipe GALAAD (futur projet commun INRIA-Université de Nice) au contrat européen GAIA. References [1] D. Lasser, Calculating the selfintersections of Bezier curves, Computers in Industry 12, 259-268, 1989. [2] L.E. Andersson, T.J Peters, N.F. Stewart, Selfintersections of curves and surfaces, Computer aided Geometric Design 15, 507-527 (1998). |
| Claude-Pierre Jeannerod | Perturbations de matrices :
algorithmes pour les cas non génériques.
On s'intéresse ici aux perturbations de matrices et au problème de l'approximation paresseuse de certains invariants (valeurs propres, sous-espaces propres) à l'aide de développements en le paramètre. De tels calculs importent en algèbre linéaire numérique - la perturbation modélise alors une erreur d'arrondi - mais aussi en calcul formel et notamment lors de la réduction symbolique de systèmes différentiels ou algébriques dépendant d'un paramètre. Résolu par Lidskii lorsque la perturbation est générique, le problème reste cependant ouvert dans la plupart des autres cas. Au cours de cet exposé nous présenterons deux algorithmes capables de traiter des familles de perturbations non génériques : pour les sous-espaces propres, il s'agit essentiellement de déterminer la solution structurée (structure Toeplitz par blocs) d'un couple d'équations algébriques de type Riccati; pour les valeurs propres, l'approche proposée consiste à minimiser par similitude polynomiale la forme de Jordan sous-jacente à la perturbation de matrice de départ. Dans les deux cas, les algorithmes ainsi obtenus trouvent une interprétation géométrique simple qui sera détaillée. |
| Raya Khanin | Symbolic-Numerical approach for solving
singular perturbation boundary value problems. In this talk I will describe the advantages of combining analytical and numerical approaches for solving singular perturbation problems, as well as the main difficulties associated with each approach if used on its own. A symbolic-numerical procedure for the initialisation of numerical solver by the leading order asymptotics of the problem will be presented. The procedure which is implemented in MATLAB/Maple environment is applied to semilinear boundary value problems. |
| Irina Kogan |
Application of the Moving Frame Method to the Symmetry Reduction of the
Differential Equations. Many systems of differential equations, especially the ones that arise in geometry and physics, possess a group of symmetry. That is, there is a group of transformations that maps solutions to the solutions. Most of the symmetric systems can be written in terms of differential invariants, and thus they can be realized as objects on the orbit space. This is the process of symmetry reduction which is, starting with S. Lie, has been widely used to obtain solutions to the differential equations. A generalisation of E. Cartan's moving frame method, developed by M. Fels and P. Olver, provide a practical tool to construct differential invariants, invariant differential forms and invariant differential operators, that is all ingredients which are used in the process of the symmetry reduction. In my talk I will review the notions of the group actions, their prolongation to the jet bundles and differential invariants. I will give examples of symmetry reduction of differential equations. After this I will show the main steps of moving frame construction of differential invariants. If there is time left, I will discuss the symmetry reduction for variational problems. |
| Sebastien Lafaille | Resolution d'equation differentielles en termes
de fonctions speciales. On s'interesse aux equations differentielles lineaires ordinaires d'ordre 2 lorsque celles-ci n'admettent pas de solutions en quadratures. Une methode recente de B.L Willis permet de trouver, lorsque cela est possible, un systeme fondamental de solution de la forme m{F_1(z), F_2(z)} ou z appartient a C(x) et F_1 et F_2 sont des fonctions speciales. A partir de l'equation lineaire consideree on genere une equation differentielle non lineaire verifiee par z. La resolution de cette derniere equation est une generalisation de l'algorithme utilise pour les equations de Riccati afin de borner les poles de z. |
| Ziming Li |
Hyperexponential Solutions of Linear PDE's with
Finite-Dimensional Solution Space We present an algorithm for computing hyperexponential (hyperexp) solutions of a linear PDE system whose solution space is finite. The algorithm consists of two major steps:
|
| Elisabeth Mansfield | A Simple Criterion for Involutivity Involutivity is a classical idea of completion of a system of PDE which considerably predates the notion of characteristic set algorithms and results. Finding the relationship between these two ideas was the aim of the speaker. There were eventually three definitions of involutivity, as discussed by Janet (1920's), Cartan (?1930's), and more recently in Spencer's survey article in 1969. Various recent texts contain modern discussions of these; e.g. PJ Olver, Storkmark, Exterior Differential Systems by Bryant, Chern, Gardner, Goldschmidt and P.A. Griffiths, and finally by Pommaret. I discuss Spencer's definition of involutivity of a system of PDE which involves a homological criterion. I show an equivalent definition which allows one to compare the calculations which verify involutivity with calculations common in computational algebra, in particular those relating to syzygies. This provides a mechanism whereby we can try to understand involutivity of PDE from a strictly algebraic point of view. The precise relationship between my criterion and the more geometric definition of Cartan is not altogether clear (to me). Note that a translation of Janet's algorithm of completion to involutivity for PDE, to polynomial ideals, is currently being investigated by authors such as Apel and Gerdt. There are several fascinating questions and potential applications and I will discuss some of them, time permitting. |
| Marc Moreno Maza | PARDI! In this I will present a joint work with F. Boulier and F. Lemaire (LIFL, University of Lille 1). We propose a new algorithm for converting a characteristic set of a prime differential ideal from one ranking into another. This differential algebra algorithm computes characteristic sets by change of ranking (ordering) for prime ideals. It identifies the purely algebraic subproblems which arise during differential computations and solves them algebraically. There are two improvements w.r.t. other approaches: formerly unsolved problems could be carried out; it is conceptually simple. Different variants are implemented. |
| Alban Quadrat | Intégrabilité formelle des systèmes différentiels:
Calcul formel et Applications en automatique Lorsque l'on étudie un système général d'équations aux dérivées partielles, il est intéressant de pouvoir connaître la dimension de l'espace de solutions du système - séries formelles ou fonctions analytiques - sans avoir à intégrer explicitement le système. Pour cela, nous devons déterminer quelles sont les dérivées que l'on doit fixer à chaque ordre afin de pouvoir développer une solution en série. Cela ne peut être mené à bien que si, à partir des équations du système, on connaît toutes les relations différentielles pour un ordre donné, c'est-à-dire si l'on n'obtient pas d'équations d'ordre plus bas par combinaisons différentielles des équations du système. Un tel système est appelé formellement intégrable et un développement en série peut alors être obtenu en fixant au départ des valeurs numériques pour un certain nombre des dérivées bien déterminées des variables du système. Ce problème a été étudié par E. Cartan (systèmes extérieurs 1900), C. Riquier et M. Janet (1900-1930), J.F. Ritt et E.R. Kolchin (algèbre différentielle 1950-1970) et, plus récemment, par l'école de D.C. Spencer (théorie formelle des équations aux dérivées partielles 1965-1970). Le concept d'intégrabilité formelle se retrouve aussi au coeur des bases de Gröbner (1965-1970) qui ont été développées pour l'étude des systèmes polynomiaux ou, plus récemment, pour les systèmes linéaires d'équations aux dérivées partielles à coefficients polynomiaux. Quelques applications de l'intégrabilité formelle sont l'étude des groupes de symétries des solutions d'équations aux dérivées partielles (groupes et pseudo-groupes de Lie), l'intégration symbolique (calcul formel, théorie de Galois différentielle) ou la physique mathématique (mécanique, électromagnétisme, relativité...). Le but de cet exposé est d'illustrer, par des exemples très simples, le concept d'intégrabilité formelle d'un système différentiel, de montrer comment rendre tout système formellement intégrable et de calculer sa dimension. Nous montrerons que les problèmes d'intégrabilité formelle se trouvent au coeur de nombreux problèmes liés à l'automatique non-linéaire (étude de la platitude des systèmes, calcul du rang différentiel, inversibilités, calcul du comportement entrée-sortie, élimination des variables latentes, contrôlabilité, observabilité, identifiabilité...), au calcul inverse des variations ou aux méthodes effectives de l'analyse algébrique. Finalement, nous montrerons comment la programmation des différents algorithmes liés à l'intégrabilité formelle, ainsi que l'utilisation des techniques effectives de l'algèbre différentielle maintenant accessibles dans Maple 6, permettent actuellement de développer une boîte à outils pour l'aide à l'analyse et à la synthèse des systèmes de contrôle non-linéaires. |
| Christophe Ritzenthaler | Courbes et automorphismes
1ere partie : les automorphismes des courbes modulaires X(q) sur C, q premier, sont bien connus : ils forment un groupe isomorphe a PSL_2(Z/qZ). Il est alors etonnant qu'en reduisant ces courbes sur des corps finis on puisse obtenir comme Adler et Kuribayashi l'ont montre des groupes plus "gros", par exemple le groupe de Mathieu M_{11} pour X(11) en caracteristique 3. Le but de l'expose est de voir a quelles conditions sur q et p de tels phenomenes peuvent se produire. Le calcul de certains invariants permettra de se pencher sur des questions de nature plus effective et la presence du groupe de Mathieu de s'interroger sur un lien avec les codes de Golay. 2eme partie : problemes generaux sur les courbes sur des corps finis : points rationnels, automorphismes, absolue irreductibilite. En particulier comment retrouver la courbe de genre 5 avec 13 points rationnels sur F_3 ? Et peut-on ameliorer les algorithmes d'absolue irreductibilite pour les courbes avec un grand nombre de points rationnels? |
| David Rupprecht | Factorisation absolue d'un polynome et quelques generalisations
Dans cet expose, nous commencerons par detailler un nouvel algorithme de factorisation absolue d'un polynome. Cette algorithme a la particularite d'etre un algorithme hybride (c'est a dire moitie numerique et moitie exact). Nous verrons ensuite quelques generalisations possibles de cet algorithme notamment dans le cas de separations de composantes irreductibles, mais encore une utilisation possible pour calculer des factorisations approchees. |
| Mohab Safey el Din | Résolution réelle des systèmes polynomiaux en dimension
positive.
L'étude des solutions réelles des systèmes polynomiaux en dimension positive est cruciale pour résoudre à terme les systèmes d'équations et d'inégalités polynomiales, et les problèmes d'élimination des quantificateurs. Après avoir expliqué pourquoi une définition de "résolution réelle" en dimension positive peut raisonnablement être la donnée d'un point par composante connexe sur la variété réelle étudiée, je montrerai en quoi les algorithmes de complexité asymptotiquement optimale et antérieurs aux travaux effectués pendant ma thèse ne sont pas satisfaisants. J'exposerai alors deux algorithmes inspirés de ce qu'on appellera la "méthode des points critiques". Dans le cas d'une hypersurface, ils différent dans la stratégie utilisée pour gérer la présence de singularités. Le premier effectue une déformation infinitésimale pour se ramener au cas lisse. Le second effectue une étude itérée du lieu singulier et traite donc directement le cas des systèmes polynomiaux. Je montrerai en quoi ces deux stratégies influent sensiblement sur le comportement pratique de ces algorithmes, ce qui sera illustré par de nombreux résultats expérimentaux. Si le temps le permet, j'exposerai quelques perspectives et applications de ces travaux (en particulier pour l'étude des problèmes de stabilité de systèmes algébro-différentiels). |
| Mike Stillman |
Computation in toric and projective geometry and homological algebra
using Macaulay2
Macaulay 2 is a specialized system for computing in algebraic geometry and commutative algebra (and related fields). The system is under active development, is freely available for linux, MacOS, Windows, and other systems, and is being used by many researchers. Dan Grayson (of University of Illinois) and I have been working on this project since 1993. Using examples from toric ideals, and projective curves, we show some ways that Macaulay2 can be used to aid research in algebraic geometry. For one example, we will take a "mystery" projective curve, and attempt to understand the structure of this curve. We will not assume any advanced knowledge of algebraic geometry in this talk. One goal of the talk is to give some idea of what Macaulay2 is capable of. We will also describe some of the ways in which Macaulay2 differs from other programs, such as Cocoa and Singular. |
| Agnes Szanto |
Solution of Degenerate Polynomial Systems over the Complex Field
The main emphasis of the talk is to find the set of complex roots of polynomial equations systems in degenerate cases, i.e. when the codimension of the algebraic set and the number of defining equations are not equal. First, I investigate a representation for algebraic sets originally proposed by Michael Kalkbrener. This representation gives an alternative to Groebner bases for many applications, and is suitable for deriving improved time and space complexity bounds. Although the computation of Kalkbrener's representation appeared to be more efficient in practice than Groebner bases techniques, but it was not known if there exists sub-exponential worst case complexity bound. I will describe new algorithms both for the computation of Kalkbrener's representation and for conducting geometric operations on algebraic sets using Kalkbrener's representation. To compute Kalkbrener's representation, I describe methods based on the sparse elimination theory of Gelfand, Kapranov and Zelevinsky. These methods exploit the sparseness of the input polynomials and in the dense representation of the polynomials I could prove sub-exponential complexity bounds. Moreover, using Kalkbrener's representation, I present efficient parallel algorithms for geometric operations on algebraic sets, generalizing the zero dimensional "lazy factorization" algorithms of Teitelbaum to higher dimensions. |
| Barry Trager | Computing the Genus of an Algebraic Curve We present an algorithm for computing the genus of an algebraic function field over a computable ground field of characteristic zero which does not require algebraic extensions of our ground field. The complexity of this algorithm is not dependent on the nature of the singularities of the given presentation of the field. Instead of relying on computing Puiseux expansions or blowing up singularites, we make use of the linear homogeneous differential equation satisfied by a suitable generator of our algebraic function field. The indicial equations of this differential equation at the discriminant locus can be used for computing the degree of the branching divisor and thus the genus via the Hurwitz formula. These indicial equations must have rational roots and thus rational coefficients. The sum of the fractional parts of these roots gives the degree of the branching divisor and subtracting the degree of the extension and adding one yields the genus of the algebraic function field. |
| Félix Ulmer | Une formule pour les solutions Liouvilliennes
d'equations lineaires d'ordre 3
On presente brievement une version simple de l'algorithme de Kovacic pour les equations differentielles d'ordre 2 dans le but de l'etendre aux equations d'ordre 3. Le but est un algorithme facile a utiliser par des non specialistes base sur l'algebre lineaire. |
| Helena Zakrajsek | Hermite and Laguerre recurrence. Every linear differential operator with polynomial coefficients L of order r induces the recurrence operator L such that L( \sum_{n=0}^\infty c_n P_n(x) ) = \sum_{n=0}^\infty L(c_n) P_n^{(r)}(x), where \{ P_n(x) \} is a family of hypergeometric polynomials. We consider the inverse problem in the case of Hermite and Laguerre orthogonal polynomials and give the two algorithms, which for a given recurrence operator L construct the differential operator L or find out that it does not exist. |