TERA’96

Facultad de Ciencias, Universidad de Cantabria

April, 9–12, 1996

1 Foreword.

TERA, in the meaning of “Turbo Evaluation and Rapid Algorithms”, is the name of a loosely organized project group spread over four countries (Spain, France, Germany, Argentina) and nine universities and research institutions. There are 27 collaborators in this group whose research and development activities are organized around two tasks, a practical and a theoretical one.

The practical task consists in the development of a program library which aims to represent a tool for attacking selected parametric polynomial and algebro–differential equation systems occuring in natural science applications and engineering. The theoretical task however consists in the search for a satisfactory definitive proof (i.e. a proof independent of conjectural open problems in theoretical computer science) that only very exceptional, “well suited”, equation systems allow an efficient treatment. This means the impossibility to construct a general purpose software solving any polynomial or algebro-differential equation system in a reasonable amount of time and memory space. Let us mention – by the way– that solving any one of these tasks is also subject of an award, the “Jacques Morgenstern Challenge”, set up by the University of Cantabria with the collaboration of a large number of other scientific organizations.

The aim of TERA’96 workshop – first in its kind– was twofold : on one hand our purpose was to bring together the european part of the TERA group in order to promote direct and personal exchange of ideas and information on work progress. On the other hand, we tried to invite a representative selection of outstanding specialists in the main fields of pure and applied mathematics and theoretical and practical computer science relevant for the research and development activities within the TERA project. These fields, at first glance unrelated, are subject to a unified view through our project oriented approach. All of them were represented during the workshop by at least one speaker or participant. We can roughly list these fields as : algebraic, semialgebraic and diophantine geometry, singularity theory, commutative and differential algebra, theory of invariants, diophantine approximation and transcendence theory from the side of pure mathematics, as numerical analysis, approximation theory and theoretical robotics from the side of applied mathematics and as complexity theory, computer algebra, seminumerical algorithms, data structures, programming languages and software engineering from the side of theorecial and practical computer science.

The workshop took place in Santander, Spain, during the week of april 9–12, 1996 at the Facultad de Ciencias, Universidad de Cantabria. There were 29 participants from Spain, France, Germany and Argentina. The atmosphere was active, friendly and communication was excellent, despite of the big number of different specialities which came to word.

We thank the following scientific institutions for their financial support and encouragement given to the workshop :

• GDR CNRS 1026 MEDICIS

• Vicerrectorado de Investigación, Universidad de Cantabria.

• Decanato de la Facultad de Ciencias, Universidad de Cantabria.

• Departamento de Matemáticas, Estadística y Computación, Universidad de Cantabria.

• Symbolic Algebraic Computation –Human Capital Mobility

• DGCyT, PB93–0472–C02–02

M. Giusti, J. Heintz, L.M. Pardo.

Contents

1 Foreword. 2

2 Teratogène ou TERA te gène ? 5

3 Schedule. 8

4 Abstracts. 10 4.1 Implementación de números racionales mediante la estructura de datos straight–line program. 10 4.2 Métodos simbólicos en teoría de aproximación. 10 4.3 Algorithms for algebro–geometric codes from singular curves. 12 4.4 Polynomials, matrices and algorithms with straight–line programs. 12 4.5 Résolution d’un système d’equations algebriques ayant des symétries. 14 4.6 Racines approvhées d’Abhyankar-Moh. 14 4.7 Sur la stabilité des calculs polynomiaux. 15 4.8 Factoring modular polynomials. Polynomial–size data structure for exponentially many solutions. 15 4.9 Pham systems : multidimensional Newton formula and applications. 16 4.10 Symbolic approaches to kinematics. 16 4.11 Data structures and zero tests. 20 4.12 Espacio/tiempo no relativista. 21 4.13 Courbes algébriques de genre ≥ 2 possédant de nombreux points rationnels. 21 4.14 Methode “efficace” de résolution d’équations: cas d’une hypersurface réelle, lisse et bornée. 22 4.15 Lower Bounds for diophantine approximations. 23 4.16 Time–space trade–offs in algebraic complexity theory. 23 4.17 Rational plane curves and data structures: parametrization algorithms and applications. 25 4.18 The Graeffe method in the multidimensional case and an application. 26

5 Address of participants. 27

2 Teratogène ou Tera te gène ?

M. Giusti et J. Heintz

Rien qui ne puisse induire des monstres dans ce qui va suivre … mais plutôt cette interrogation : serions-nous des gêneurs ? Il nous semble connaître déjà la réponse …

Que veut dire TERA ? Ce sigle signifie “Turbo Evaluation & Rapid Algorithms”. C’est le nom d’un projet qui regroupe une vingtaine de personnes de part le monde, et ces journées en constituent le premier rassemblement. Des esprits malins ne manqueront pas de faire observer que le préfixe tera, placé devant une unité de mesure, la multiplie par 10^{12} , représentant ainsi le carré de mega. Nous ne commenterons pas cette remarque.

Dans les années 80, l’utilisation de techniques de réécriture basées sur l’algorithme de Buchberger avait fait naître de grands espoirs quant à la résolution symbolique des sytèmes d’équations polynomiales. Le calcul formel sortait ainsi de ses domaines de prédilection d’origine, qui tournaient peu ou prou autour du cadre réduit des problèmes à une variable : PGCD, résultants, recherche de primitives, etc …

S’était ensuivie une floraison d’études des diverses variantes de cet algorithme, et dans une bien moindre mesure, l’implantation de celles-ci dans différents systèmes de calcul formel, et encore plus rarement et récemment, directement dans des langages de bas niveau pour viser plus d’efficacité. On avait même vu ainsi un projet ESPRIT BRA consacré exclusivement à la (re)fabrication et l’utilisation annoncée pratique voire industrielle d’un tel Gröbner engine, pour reprendre la terminologie même dudit projet.

Or, les fruits n’ont pas tenu les promesses des fleurs, tant s’en faut. Si l’on peut considérer que la notion de base standard et une implantation efficace de sa construction peuvent jouer un certain rôle dans l’expérimentation en géométrie algébrique, il n’en est pas de même pour des systèmes provenant du monde physique, surtout quand ceuxci sont paramétrés. Et rentre dans cette catégorie tout système faisant intervenir des quantités dont on ne connaît qu’une valeur approchée.

En pratique, même avec la meilleure implantation du moment (le logiciel GB de Jean-Charles Faugère, antérieur au projet loc. cit.), on n’est jamais sûr de franchir la barre fatidique de 10 équations à 10 inconnues. C’est loin de pouvoir répondre aux besoins.

La situation était d’autant plus préoccupante qu’il n’y avait plus grande amélioration à attendre du côté de l’algorithmique. En effet, la taille même de l’écriture des sorties produites … par ces réécritures ne permettait pas d’espérer tomber plus bas que la classe P SP ACE de complexité, d’ailleurs atteinte par les études théoriques de complexité.

Pas question de rêver à l’eldorado des algorithmes de complexité polynomiale en la taille des entrées ! Encore moins quand celles-ci comportent relativement peu de monômes, la réécriture possédant le goût douteux de densifier immédiatement tout joli petit système creux.

Pour sortir de l’impasse il fallait reprendre une vieille idée qui remonte aux commencements de la théorie algébrique de la complexité. Il s’agit de l’observation que tous les polynômes éliminants connus sont des déterminants ou des quotients de déterminants ; or les déterminants ont une longue représentation comme formule, leur écriture est également longue mais on peut les évaluer rapidement. Par conséquent la représentation de polynômes par calcul d’évaluation (au lieu de leur écriture) devrait produire une réduction considérable de la taille des objets informatiques à manipuler dans un processus d’élimination.

L’introduction de cette structure de données (notion relevant de l’informatique) dans un problème mathématique (l’élimination) est due a plusieurs personnes, parmi lesquelles on doit mentionner en tout premier lieu Jacques Morgenstern et Malte Sieveking. Mais malheureusement, l’application immédiate de cette idée simple s’était révélée beaucoup plus difficile que prévu dans ces années 70, tout simplement parce que l’évaluation rapide n’est directement héréditaire dans aucun processus d’élimination.

Ce n’est que relativement récemment, et au bout d’une décennie d’efforts, que cette difficulté a été surmontée. Il a fallu développer et adapter certaines techniques d’algèbre commutative de type “dualité” au contexte de cette nouvelle structure de données. Le gain immédiat de complexité en terme d’opérations arithmétiques était exponentiel ! Puis au sein d’un deuxième mariage arrangé avec la géométrie diophantienne, ces nouvelles techniques, complétées par une adaptation de méthodes importées de l’analyse numérique, produisaient les mêmes améliorations au niveau bit.

Ces résultats théoriques ouvraient de nouvelles perspectives pratiques : il devenait tentant de se lancer dans des implantations orientées vers les applications du calcul symbolique en ingénierie et optimisation, où prédominent les systèmes paramétrés de grande taille. En quelque sorte, il s’agit maintenant de fabriquer un moteur turbocompressé pour venir au secours de l’antique Gröbner engine atmosphérique quelque peu essoufflé.

Le projet TERA c’est donc actuellement :

– 1. La création d’une bibliothèque de programmes capables de manipuler ces nouvelles structures de données, en vue d’aboutir au traitement performant de systèmes polynomiaux d’origine et de taille industrielle, mais bien conditionnés dans un certain sens. Ceci passe par une simplification symbolique du système, qui s’adapte bien à un traitement postérieur numérique par le caractère semi-numérique des calculs d’évaluation et leurs propriétés de stabilité.

– 2. A contrario, la recherche d’une preuve théorique qu’aucune méthode UNI-VERSELLE de résolution de systèmes polynomiaux ne peut être efficace GLOBALE-MENT, par l’exhibition explicite d’un système intraitable ou par l’établissement implicite de la concordance voire la coïncidence explicite des bornes supérieures et inférieures de complexité.

– 3. S’inspirer du succès de l’utilisation des calculs d’évaluation en élimination classique pour mettre en évidence dans d’autres domaines du calcul formel le rôle crucial et largement oublié des structures de données.

Au profit terminal du calcul formel sont mises en œuvre dans ce projet des techniques de géométrie algébrique, semi-algébrique et diophantienne, de théorie des singularités, d’- analyse numérique et théorie de l’approximation, théorie de complexité dans le modèle algébrique et dans le modèle bit, complexité structurelle, analyse et manipulation de structures de données, vérification et spécification de programmes, programmation.

Ainsi se retrouvent réconciliées dans le calcul formel mathématiques et informatique, dont le face-à-face dans ce domaine bidisciplinaire a trop souvent tourné au pugilat pour des raisons plus sociologiques que scientifiques.

3 Schedule.

April, 9 , 1996

• Morning Session – 10:00h.– Reception of Participants

– 10:15h.– M. Arrate. “Welcome to our Faculty of Sciences”

– 10:30h.– M. Giusti. “TERATEGÉNE?”

– 11:30h.– Coffee break

– 12:00h.– J. Heintz.“NON, PAS DU TOUT!”

• Afternoon’s Session

– 16:00h.– J.E. Morais.“Bornes inferieures pour l’approximation diophantienne”.

– 17:00h.– J.P. Dedieu.“Sur la stabilité des calculs polynomiaux”.

– 18:00h.– Coffee break

– 18:30h.– J.C. Yakoubson.“The Graeffe method in the multidimensional case and an application”

April, 10 , 1996

• Morning Session – 10:00h.– V. Cossart.“Racines approchées d’Abhyankar–Moh”

– 11:00h.– R. Sendra.“Rational plane curves and data structures: parametrization algorithms and applications”

– 12:00.– Coffe break

– 12:30h.– A. Campillo.“Algorithms for algebro-geometric codes from singular

curves”

• Afternoon’s Session

– 16:00h.– J. von zur Gathen.“Factoring modular polynomials: polynomialtime data structures for exponentially many solutions”

– 17:00h.– L. Kulesz.“Courbes algébriques de genre ≥ 2 possédant de nombreux points rationnels”

– 18:00.– Coffee break

– 18:30h.– J.L. Montaña.“Time/Space trade–offs in algebraic complexity theory”

April, 11 , 1996

• Morning Session – 10:00h.– K. Hägele.“Data structures and zero equivalence tests”

– 11:00h.– M. Aldaz.“Implementación de test de nulidad”

– 11.30h.– Coffee break

– 12:00h.– B. Castaño, J. Llovet, R. Martínez.“Polinomios,matrices y algorit-

mos con SLP’s : una implementación”

• Afternoon’s Session – 16:00h.– R. Alvarez Nodarse.“Métodos simbólicos en teoría de aproximación”

– 17:00h.– L. Gonzalez Vega.“Pham systems: multidimensional Newton formula and applications”

– 18:00h.– Coffee break

– 18:30h.– M.J. Gonzalez López.“Symbolic approaches to kinematics”

April, 12 , 1996

• Morning Session

– 10:00h.– G. Mbakop.“Methodes “efficaces” pour la résolution de systémes d’équations polynomiales. Cas d’une hypersurface réelle”

– 11:00h.– A. Colin.“Résolution des systèmes algébriques ayant des symétries”

– 11.30h.– Coffee break

– 12.00h.– J. Heintz.“Espacio/tiempo no relativista”.

4 Abstracts.

4.1 Implementación de números racionales mediante la estructura de datos straight–line program.

M. Aldaz Zaragüeta

Se describe la forma en que se ha usado el tipo abstracto de datos SLP para representar números racionales. Para ello previamente se muestra cúal ha sido la estructura de datos elegida para soportar el DAG formado por el SLP, y cómo pueden ser usados los identificadores de nodos del DAG para representar elementos de 0 Q. La aritmética con racionales representados de este modo se reduce a operaciones de inserción de nodos en el DAG.

La posibilidad que existe de que un mismo racional pueda ser representado mediante diferentes nodos de un DAG y el poder representar racionales de talla bit 2^{n} mediante nodos en profundidad n dentro del DAG, exigen disponer de un test de comparación por igualdad que permita determinar si un nodo representa o no al valor cero sin necesidad de producir los resultados intermedios que nos llevan hasta ese valor. El test probabilístico de nulidad para enteros de Hägele-Montaña resuelve el problema produciendo resultados intermedios de talla bit máxima 2L, siendo L el número de nodos que en el DAG forman la historia previa del nodo sobre el que se aplica el test.

Este trabajo está parcialmente financiado por la ayuda foral al proyecto de investigación: “Desarrollo e implementación del tipo abstacto de datos straight–line program”.

4.2 Métodos simbólicos en teoría de aproximación.

R. Álvarez-Nodarse

En las más diversas áreas de la Teoría de la aproximación aparecen problemas relacionados con la Teoría de las funciones especiales, y en particular los polinomios ortogonales. En la mayoría de los casos el trato con dichas funciones puede ser bastante tedioso, sobre todo cuando se desean estudiar y conocer diversas propiedades analíticas de las mismas (relaciones de recurrencia, representaciones en términos de otras funciones, propiedades espectrales,...). El gran desarrollo de paquetes de cálculo simbólico, como por ejemplo: Mathematica, Maple, Reduce, Derive, Axiom,..., puede, en muchos casos, ahorrar una gran cantidad de tiempo y trabajo.

Existen un sinúmero de publicaciones y algoritmos para el tratamiento simbólico de diversos problemas de aproximación. Por ejemplo: El paquete Mathematica incluye varios comandos simbólicos para estudiar diversos tipos de interpolación, series, etc. G. Gasper [G,90] describe como utilizar Mathematica para demostrar y deducir diversas fórmulas y relaciones entre diferentes funciones hipergeométricas y q− series básicas r φ_{p} y diferentes familias de polinomios ortogonales asociadas a ellas. W. Koepf [K,94] ha desarrollado diversos algoritmos simbólicos para tratar funciones especiales, los polinomios ortogonales y series de potencias de la forma: F (x) = ∑_{k=k_{0}}^{∞} a_{k}x^{k/n}, etc., los

cuales complementan los paquetes estándard de los programas antes mencionados.

En este seminario se expondrán ideas básicas acerca de cómo los paquetes simbólicos de las álgebras computacionales pueden ayudarnos a encontar ecuaciones diferenciales o en diferencias de segundo orden (EDSO) para casos más generales que polinomios ortogonales clásicos: Los denominados polinomios generalizados de tipo Krall. También mostraremos como, utilizando algoritmos generales podemos a partir de los coeficientes de las EDSO, obtener fórmulas analíticas para los momentos de la distribución de ceros μ_{r} y de la densidad de la distribución de ceros ρ_{n}(x) definidos por

μ_{r} = \frac{1}{n}y_{r} = \frac{1}{n} ∑_{i=1}^{n} x_{n,i}^{r}, ρ_{n}(x) = \frac{1}{n} ∑_{i=1}^{n} δ(x − x_{n,i})

donde x_{n,k} denota los ceros de las soluciones de la EDSO, y muy útiles en diversos problemas de aplicación práctica. Dichos algoritmos fueron desarrollados por Dehesa et al. ([BDG,88],[DYZ ,95]) y son fácilmente implementables en cualquiera de los paquetes simbólicos antes mencionado ([A-NM,95],[A-NM,96]).

Referencias

[G,90].— G.Gasper . “Using Symbolic Computer Algebraic System to Derive Formulas Involving Orthogonal Polynomials and Other Special Functions”. En Orthogonal Polynomials. Theory and Practice. P. Nevai ed., Vol. 294, (Kluwer Acad. Publ., Dordrecht, 1990), 163-179. [K,94].— W. Koepf. Algorithmic Work with Orthogonal Polynomials and Special Functions. Preprint SC 94-5, 1994. [DYZ ,95].— A.Zarzo, J.S. Dehesa and R.J. Yañez.“ Distribution of zeros of Gauss and Kummer hypergeometric functions: A semiclassical approach”. Annals Numer. Math. 2 (1995) 457-472. [BDG,88].— E. Buendía, S.J. Dehesa and F.J. Gálvez. “The distribution of the zeros of the polynomial eigenfunction of ordinary differential operators of arbitrary order”. Lecture Notes in Mathematics, Vol. 1329, Springer-Verlag, Berlin, 1988, 222-235. [A-NM,95].— R. Álvarez-Nodarse and F. Marcellán.“The limit relations between generalized orthogonal polynomials”. (sometido a Indag. Math. 1995) [A-NM,96].— R. Álvarez-Nodarse and F. Marcellán. “A generalization of the classical Laguerre polynomials II. Zeros, Second order differential equation and three term recurrence relation”. (a aparecer en Appl. Analysis. 1996.)

4.3 Algorithms for algebro-geometric codes from singular curves.

A. Campillo

Several algorithms for coding and decoding algebro- geometric codes constructed from singular curves over finite fields are presented and discussed. The main ingredients are computations for rational parametrizations of branches, for approximate roots at infinity and for graded rings with respect to valuations.

4.4 Polynomials, matrices and algorithms with straight–line programs

B. Castaño, J. Llovet, R. Martínez

The aim of this contribution is to compute, using the Berkowitz algorithm [B,84], [J,94] the determinant and the characteristic polynomial of a matrix of multivariate polynomials over ZZ . When there are a large number of variables and monomials, this computation produces a huge number of terms. This class of polynomials is impossible to manage in any traditional system of representation because this implies a high degree of difficulty when we only want to determinate if the value of the polynomial is zero. We propose an alternative approach to solving this problem. The method is based on the use of straight–line programs [GHMMP,95] (slp’s) for for the representation of any intermediate result of computation. This contribution describes a computation prototype (TERA) that shows the efficiency of the proposed approach.

We first show the basic concepts that allow us to construct a data structure representing multivariate polynomials given by straight–line programs. The objective is to minimize the number of parallel arithmetic operations involved in polynomial evaluation. The representation and formal treatment of straight–line programs is done by means of an abstract data structure that supports the inputs, scalars, operations and elements of the computation sequence in the straight–line program. A directed acyclic graph (dag) is a valid structure for representing a straight–line program. To construct and manipulate a dag by computer, with these characteristics, we have developed a special coding for nodes. This allows us to establish the semantic of the straight–line program. We build a two-dimensional physical data structure, called representational data structure, to implement the formal structure directed acyclic graph representing the polynomial. This obeys two construction rules: Repeated nodes are disallowed and the dag depth is minimized. The representational data structure, constructed in this way, is non-linear and therefore not suitable for the evaluation of the polynomial associated with it. In fact, using a pebble game strategy we construct a second data structure, called evaluation data structure, which is a one-dimensional array, easier to run, in order to compute the value of the given polynomial at a fixed point (cf. [AHMMP,96]).

The pebble game evaluates the nodes in breadth-first order, therefore all nodes of the same depth have to be pebbled simultaneously before the first node of the following depth can be pebbled. A pebble is removed when it is no longer needed. In this game any node is only once pebbled which means that the algorihtm minimizes computation time. We build dags to represent matrices with polynomial entries using the same criteria as for the representation of multivariate polynomials. Input nodes represent the variables of the polynomials from which we generate a dag representing each polynomial appearing as entry of the given matrix. The complete dag, thus constructed, has as many output nodes as entries in the given matrix. Every output node represents a multivariate polynomial. The evaluation process of dags with several outputsis analogous to the evaluation process of simple output dags.

The next step is to build dags representing algorithms. In this case, we use the Berkowitz algorithm for computing the characteristic polynomial of a matrix. The input nodes of the dag of the Berkowitz algorithm are the output nodes of the dag representing the matrix of multivariate polynomials. The process ends with the construction of a dag which codifies by its output nodes the coefficients of the characteristic polynomial of the given matrix.

The input nodes of this final dag are the variables ( x_{1}, x_{2}, …, x_{n}) of the polynomials appearing as entries of the given matrix. The output nodes are the coefficients of the characteristic polynomial of the given matrix. In fact, the determinant is the coefficient of zero degree. This dag represents the characteristic polynomial of the given polynomial matrix and allows an evaluation of its characteristic polynomial using less resources than algorithms using a conventional dense representation. Morover, this representation is well suited for the applications of numerical methods.

We have implemented all these structures and algorithms in a prototype, called TERA, running on a PC under MSDOS. TERA allows us to build, view, and evaluate dags representing multivariate polynomials, polynomial matrices and the Berkowitz algorithm to determine characteristic polynomial and determinants of the given polynomial matrices. TERA uses only relatively little memory (640 Kb) and it can run with polynomials of up to 26 variables (A,B, ..., Z). It can also compute characteristic polynomials of 12x12 matrices , matrices with an associated dag of 22288 nodes.

We have compared the performance of TERA with other traditional computer algebra systems, such as Maple. We generate random polynomials in 8 variables, with 10 monomial terms of total degree 3, and build matrices with these polynomials, we compute their characteristic polynomials using Maple. The system is unable to run computations for 4x4 or larger matrices because intermediate expressions become too large to handle. The TERA program runing in the same input data returns the result in a few seconds using 1000 nodes o less. With 10x10 and 11x11 matrices, TERA is able to carry out the same type of computations successfully.

References

[B,84].— S.J. Berkowitz.“On computing the determinant in small parallel time using a small number of processors”, Inform. Process. Letters, 18, pp, 147-150 (1984). [GHMMP,95].— M. Giusti, J. Heintz, J.E. Morais,J. Morgenstern, L.M. Pardo.“Straight–line Programs in Geometric Elimination Theory”, to appear in J. of Pure and App. Algebra (1996). [AHMMP,96].— M. Aldaz, J. Heintz, G. Matera, J.L. Montaña, L.M. Pardo. “Time-Space Tradeoffs in Algebraic Complexity Theory”. Preprint 1996 (cf. also this issue). [J,94].— A. Jounaidi. “Sur l’algorithme de Berkowitz poue le calcul du déterminant dans un anneau commutatif arbitraire”,Equipe de Mathématiques de Besançon, n. 25, 1994.

4.5 Résolution d’un système d’équations algébriques ayant des symétries.

Antoine Colin

Nous proposons une méthode pour résoudre les systèmes d’équations polynomiales dont les équations sont invariantes par les permutations d’un certain sous-groupe G du groupe symétrique S_{n}. Elle consiste à exprimer les équations à l’aide d’invariants primaires Π_{1}, …, Π_{n} (par exemple les polynômes symétriques élémentaires), et d’un unique invariant secondaire “primitif”. Les invariants primaires forment une base de transcendance de l’algèbre des invariants de G, et les puissances de l’invariant primitif constituent une base du corps des invariants de G considéré comme un espace vectoriel sur k(Π_{1}, …, Π_{n}) . Les solutions du système sont alors données comme racines de polynômes dont les coefficients eux-mêmes sont donnés comme racines d’autres polynômes : la représentation des solutions (x_{1}, …, x_{n}) casse l’extension de corps k(x_{1}, …, x_{n}) : k en deux.

4.6 Racines approchées d’Abhyankar-Moh.

Vincent Cossart (en collaboration avec G. Moreno–Socias)

Dans cette conférence, nous avons défini les racines approchées d’Abhyankar-Moh, un algorithme simple permet de les calculer effectivement. Ces racines permettent de calculer les invariants d’une courbe plane singulière analytiquement irréductible, l’implantation de ce calcul est faite en MAPLE, une implantation comme “straight–line program” devrait fournir l’algorithme le plus rapide qui soit.

Nous avons montré sur un exemple que ces racines permettaient également de donner un critère d’irréductibilité analytique d’une courbe plane. Ce critère devrait pouvoir être implanté sous forme de “straight–line program” et devrait être très efficace.

Enfin, ces techniques devraient pouvoir être appliquées dans de nombreux cas en caractéristique positive.

4.7 Sur la stabilité des calculs polynomiaux.

J.P. Dedieu

Après avoir introduit les nombres réels flottants, nous donnons trois théorèmes de stabilité. Le premier est un résultat classique du à Wilkinson sur la stabilité de la résolution d’un système d’équations linéaires par la méthode d’élimination de Gauss en virgule flottante. Ce résultat fait appel au concept d’erreur rétrograde dont nous disons un mot.

Le second résultat, du à l’auteur, analyse l’erreur commise lors de l’évaluation d’un polynome multivarié. Ici encore on utilise la notion d’erreur rétrograde. Ce résultat fait apparaitre que l’erreur commise dépend de façon essentielle de trois nombres qui sont : l’unité d’arrondi, le nombre de variables et la profondeur de l’algorithme. Enfin on expose un résultat du a Malajovich sur la stabilité du calcul des racines d’un système polynomial par la méthode de Newton. Ce résultat prouve que, sous des hypothèses classiques, cette méthode converge vers un ensemble centré en une des racines et dont le diamètre dépend à la fois du conditionnement du système et de l’unité d’arrondi.

4.8 Factoring modular polynomials. Polynomial–size data structure for exponentially many solutions.

Joachim von zur Gathen (Joint work with Silke Hartlieb)

This talk presents an algorithm to factor a polynomial f (in one variable) over a residue class ring of ZZ or IF_{q}[y] , modulo a ring element r. The Chinese Remainder Theorem reduces our problem to the case where r is a prime power. Then factorization is not unique, but if r does not divide the discriminant of f , our (probabilistic) algorithm produces a description of all (possibly exponentially many) factorizations into irreducible factors in polynomial time. This is achieved by means of a data structure that keeps track of all solutions of certain systems of linear equations modulo prime powers. If r divides the discriminant, we only know how to factor by exhaustive search, in exponential time.

An Extended Abstract is to appear in Proc. ISSAC 96, Zürich, 1996.

4.9 Pham systems: multidimensional Newton formula and applications.

L. González Vega

This talk is devoted to present, following the idesas of Kytmanov andAizenberg, a fully algebraic generalization of the classical Newton–Waring identities to the multivariate case when the zero dimensional ideal under consideration is a complete intersection and every equation of the system has the following structure:

F_{j}(x_{1}, …, x_{n}) = x_{j}^{d_{j}} + Q_{j}(x_{1}, …, x_{n})

with deg(Q_{j}) < d_{j}.

We apply these identities to the following two problems :

• Elimination Theory: the computation of the implicit equation for parametric surfaces.

• Interpolation Theory: the computation of all the poised matrices in the Birkhoff Interpolation Problem for n ≤ 4 .

Let us also mention that an efficient representation and manipulation of polynomials depending on parameters would produce a more efficient solution of these problems.

4.10 Symbolic approaches to kinematics.

M.J. González López

For many geometrical problems in robotics, such as direct and inverse kinematics, design and analysis of robots, motion planning, path tracking, etc., we have to find the solution of kinematic equations that involve three kinds of variables:

• variables ( X) that describe the inner state of the robot joints (for instance, the angle that an arm rotates with respect to another arm), • variables ( P ) that describe the location of a distinguished body of the robot with

respect to some universal, fixed, reference frame (for instance, the location of an end-effector in a robot manipulator), and

• variables ( D) that correspond to the parameters of the robot class under consideration (for instance, the lengths of the arms of a 6R manipulator).

Kinematic equations are usually obtained by commonly accepted algorithmic methods [DH, 55], and converted to non linear polynomial equations in X, P and D. The common question from the symbolic point of view in the above mentioned problems is to describe (symbolically) the relation between X and P in the simplest possible way, and how this relation changes for different values of D. This process is oriented to obtain in an effective way the real solutions of the kinematic equations for any specialization of some blocks of variables: for example, a concrete robot is given when we fix its robot class parameters to a specific value D_{0} , and solving its inverse kinematics consists in obtaining all the real solutions of the kinematic equations in the variables X for any given value P_{0} .

It is important to remark that the big number of variables involved in these problems is one of the most significant obstacles to find effective symbolic solutions. For example, the variety defined by the kinematic equations of the 6R manipulator has dimension 24, and it is usually embedded in IR^{48} . The variety corresponding to a concrete robot inside the 6R class has dimension 6 and it is usually embedded in IR^{24} ; and for almost all the values P_{0} this variety is 0-dimensional, and embedded in IR^{12} . This character has made us to devote some effort to know if it is possible to replace the kinematic equations (classically used for every robot class) by others simpler yielding the same set of real solutions. We have proved that it is not possible for the most usual classes of robots: parallel robots and manipulators with prismatical, revolute, spherical or universal joints, as their corresponding kinematic equations generate real and prime ideals (see [GR, 94], [GR, 95]). Other approach to simplify kinematic equations is to apply a functional decomposition procedure to some of the equations, obtaining others of lower degree ([K, 91]). This method have found good results in very particular cases of sine-cosine polynomials ( [GuR, 94]).

We have also treated a special block of polynomials that appear always inside the kinematic equations of any robot class, which are those describing the special orthogonal group SO(3) ; these polynomials are obtained imposing a 3 × 3 matrix with indeterminated coefficients to be proper orthogonal. Although there are several ways to describe this group (with quaternions, skew-symmetric matrices, etc.) we propose to use a set of polynomials called Weyl basis of SO(3) , which have good computational properties ([GR, 93b]) and have been helpful to get a Gröbner basis of some polynomials coming from the Stewart Platform equations ([L, 93]).

Once obtained and simplified the kinematic equations, different symbolic methods have been applied to describe their solutions. Any of them has given the expected global solution for all the robot classes, although they have helped to understand the special structure of the equations, and some of them have been useful in particular aspects of particular robots (as bounding the number of solutions, partitioning the space of robot class parameters finding important subclasses, or rewriting the equations into others more interesting from the computational point of view). We finish this abstract making a resume of the most usual methods and remarking the profit found on every one.

i) The Cylindrical Algebraic Decomposition (CAD) algorithm ([BCR, 86]) yield a partition of the variety corresponding to the (D,P) variables, and over each piece, it gives a way of determining the corresponding values for the X variables. This method is usually of no practical value at the present state of the art concerning the performance of the CAD algorithm.

ii) Gröbner basis over a suitable field extension of IR (where the kinematic equations describe a zero dimensional variety) perform a triangularization of the equations. This approach, initiated by [B, 89], may fail to give a complete answer for some numerical values of the variables considered in the coefficient field, since the evaluation of these special values of the obtained triangular system can fail to yield a triangular system with numerical coefficients, or perform prohibited computations ([CLO’S, 92], [GR, 93a]). Besides, the big number of variables used has made that none of the computer algebra software used (Axiom, CoCoa, GB, Macaulay, Maple, etc.) have solved generic and global problems for the industrial robot classes. However, there is a remarkable result achieved with Gröbner basis computations, which is the bound for the number of (complex) direct solutions of the general Stewart Platform ([L, 93] proved that if this number is finite, then it is at most 40).

iii) Dynamic Evaluation Techniques ([D^{4} , 85]) and Comprehensive Gröbner Basis ([W, 92]) are also rewriting rules to perform triangularizations of the given equations that avoid the specialization problems stated in b). Although the implementations of these algorithms have not given good results when applied to the general robot classes, we have performed (by hand, with some simple heuristics) the Dynamic Evaluation process to a specific robot with five rotational degrees of freedom, obtaining interesting practical results ([GR, 93a]).

iv) Elimination techniques based on the ideas from [C, 1848] “remain computationally too costly to be applied to the types of multivariate polynomial problems which are common in kinematics”, as stated in [R, 93]. This same author proposes in [RR, 89] one modification of the Sylvester’s dialytic elimination method [S, 1885] that solves the inverse kinematics problem for the 6R manipulator robot class.

As conclusion, none of the tested symbolic methods is able to solve the kinematic problems proposed in all their generality, but they have been very useful in certain problem areas. Although the main obstacle comes from the high dimensional varieties associated to these problems, it is also remarkable that the proposed methods do not profit the special structure of the kinematic equations, nor the important difference between the types of variables that appear. If these characteristics are taken into account (by performing particular heuristics for particular robot classes or concrete robots) interesting and practical results can be found.

References

[BCR,86].— J. Bochnak, M. Coste, M.F. Roy. “Géométrie Algébrique Réelle”. A Series of Modern Surveys in Mathematics. Vol. 12 Springer Verlag, 1.986. [B, 89].— B.Buchberger. “Applications of Gröbner basis in non-linear computational geometry”. Trends in Computer Algebra. Lecture Notes in Comp. Sci. 296. Springer Verlag (1.989). [C, 1848].— A. Cayley. “On the theory of elimination”. Cambridge and Dublin Mathematics Journal, v. 3, (1848). [CLO’S, 92].— D. Cox, J. Little, D. O’Shea. “Ideals, varieties and algorithms”. Undergraduate Texts in Mathematics. Springer Verlag. (1992). [D^{4} , 85].— J. Della-Dora, C. Dicrescenzo, D. Duval. “About a new method for computing in algebraic number fields”. EUROCAL’85 vol. 2. G. Goos, J. Hartmanis Eds. Lecture Notes in Comp. Sci. 204. Springer Verlag. (1985). [DH, 55].— J. Denavit, R. S. Hartenberg. “A Kinematic Notation for Lower-Pair Mechanisms Based on Matrices”. ASME Journal of Applied Mechanics, (1955) 215–221. [GR, 93a].— M.J. González-López, T. Recio. “The ROMIN inverse geometric model and the dynamic evaluation method”. Computer Algebra in Industry. A. M. Cohen Ed. Wiley and Sons Ltd. (1993) 117–141. [GR, 93b].— M.J. González-López, T. Recio. “Formal Determination of Polynomial Consequences of Real Orthogonal Matrices”. Recent Advances in Real Algebraic Geometry and Quadratic Forms: Proceedings of the RAGSQUAD Year. Contemporary Mathematics Series, Vol.155, (1993).

[GR, 94].— M.J. González-López, T. Recio. “On the symbolic insimplification of the general 6Rmanipulator kinematic equations”. ACM Proceedings ISSAC’94, (Oxford) (1994).

[GR, 95].— M.J. González-López, T. Recio. “On the reality of inverse kinematic ideals”. Contributions to General Algebra 9. Verlag Hölder-Pichler-Tempsky, Wien (1955) 183-196. [GuR, 94].— J. Gutiérrez, T. Recio Advances in the simplification of sine-cosine equations. Preprint Univ. Cantabria, (1994). [K, 91].— P. Kovács. “Minimun degree solutions for the inverse kinematics problem by application of the Buchberger algorithm”. Advances in robot kinematics. S. Stifter and J. Lenarcic Eds, . Springer Verlag. (1991) 326–334.

[L, 93].— D. Lazard. “Generalized Stewart platform: How to compute with rigid motions?”. IMACS SC, (1993). [RR, 89].— M. Raghavan, B. Roth. “ Kinematic analysis of the 6R manipulator of general geometry”. International Symposium on Robotics Research, Tokio, (1989) 314–320. [R, 93].— B. Roth. “Computations in Kinematics”. Computational Kinematics. J. Angeles, G. Hommel and P. Kovács Eds. Kluwer Acad. Pub., (1993). [S, 1.885].— G. Salmon. “Higher Algebra, 5th Edition, reprinted Chelsea Publishing Co. NY, (1964). [W, 92].— V. Weispfenning. “Comprehensive Gröbner basis”. J. Symb. Comp. 14/1, (1992) 1-29.

4.11 Data structures and zero tests.

K. Hägele

In this talk some ideas are given why we consider complexity and the choice of the right data structure as important points in the development of our algorithms, and present a practical and efficient solution to some of the problems appearing when working with these data structures, called straight–line programs.

We consider examples from Numerical Analysis, Diophantine Approximation, Elimination Theory and Linear Algebra, where the classical ways of representing numbers (the binary system or a fixed precision floating point system) as general-purpose methods result in algorithms of exponential complexity, whereas a well-chosen special-purpose solution (straight–line programs for numbers) gives far better complexity bounds.

One central point of interest in these cases is the zero-equivalence-test of the resulting straight–line programs. A sketch of the main ingredients for a practical “zeroequivalence test for numbers given by straight–line programs” is given as a partial result of a joint work with José Luis Montaña from the Public University of Navarra.

The zero-equivalence test is based on a arithmetic version of the Heintz-Schnorr Theorem [HS,80], stating the existence of many universal short test sequences for the class of straight–line programs for numbers of a fixed complexity. The derived test is a practicable non-uniform BPP complexity class algorithm which allows easy implementation.

References

[HS,80].— J. Heintz and C. P. Schnorr. “Testing Polynomials wich are easy to compute”, Proc. 12th Ann. ACM Symp. on Computing (1980) 262-268.

4.12 Espacio/tiempo no relativista.

J. Heintz

Se presenta la descripción de un programa que es capaz de determinar el rango de una matriz sobre los enteros en espacio de memoria polilogarítmico en el tamaño de la matriz y de sus entradas que son dadas en representación bit. Este programa es también capaz de calcular cualquier bit requerido del determinante de la matriz con el mismo coste de espacio de memoria si la matriz es cuadrada. El trabajo de implementación está basado en una reinterpretación novedosa de un viejo resultado de A. Borodin que dice que una familia POLYLOGSPACE–uniforme de redes booleanas de profundidad polilogarítmica y de tamaño polinomial puede ser transformada en un algoritmo que calcula el mismo resultado y que usa solamente espacio polilogarítmico. Esta interpretación se debe al trabajo de G. Matera y J.M. Turull [MM,96] y su motivación consiste en encontrar algoritmos eficientes en espacio para la tarea de resolver sistemas de ecuaciones polinomiales eficazmente.

El trabajo de implementación fue realizado en el Departamento de Computación de la Universidad Nacional de San Luis (Argentina) por Alejandro Grosso, Norma Herrera y María Eugenia Stefanoni. El programa representa (a mi conocimiento) la primera demostración de la uniformidad POLYLOGSPACE de un algoritmo en álgebra lineal.

Referencias

[MM,96].— G. Matera, J.M. Turull. “The Space Complexity of Elimination Theory : Upper Bounds”, Accepted for presentation at FOCM’97, Rio de Janeiro (1997) .

4.13 Courbes algébriques de genre ≥ 2 possédant de nombreux points rationnels.

Leopoldo Kulesz

En 1983 G. Faltings montre que pour tout corps de nombres K, les courbes algébriques sur K de genre ≥ 2 possèdent au plus un nombre fini de points K -rationnels. Dès lors, la problématique est de savoir combien il y en a et comment ils sont distribués.

Des conjectures énoncées par S. Lang il y a quelques années impliquent entre autres que pour tout corps de nombres K et tout genre g ≥ 2 il existe une borne B(g, K) telle que toute courbe de genre g sur K possède moins de B(g, K) points K -rationnels.

Pour analyser ces conjectures nous nous proposons d’explorer des bornes inférieures de l’éventuel B(g, K) . Nous exposerons alors différentes constructions de courbes algébriques de genre g ≥ 2 avec de nombreux points rationnels et en particulier pour K = Q et g = 2, 3, 4 et 5 .

4.14 Methode “efficace” de résolution d’équations: cas d’une hypersurface réelle, lisse et bornée.

G. Mbakop (Joint work with B. Bank, M. Giusti, J. Heintz, R. Mandel)

Nous présentons dans ce travail une nouvelle méthode d’application au cas réel des polynômes à plusieures variables, des algorithmes dévelopés respectivement dans [GHMP,95], [GHMMP,95], et [GHHMMP,96] qui déterminent les zéros complexes d’un système d’équations polynomiales donné par un calcul d’évaluation (straight–line program). Le cas á étudier dans cet exposé est celui d’une hypersurface compacte réelle, lisse et bornée, dont une équation régulière par un polynôme à plusieures variables et à coefficients rationnels est donnée. Les models de calcul sont ceux des réseaux arithmétiques (arithmetic network) et nos résultats consistent en la détermination d’au moins un représentant réel sur chaque composante connexe de l’hypersurface étudiée.

i) soit f ∈ 0 Q[X_{1}, …, X_{n}] sans carré, de degré d ≥ 2 donné par un calcul d’évaluation (straight–line program) β sans division essentielle et de longueur non scalaire L, qui code les entrées de nos algorithmes. Soit f une équation régulière d’une hypersurface lisse et compacte de IR^{n}, et soit δ une borne supérieure des degrés de certaines variétés polaires associées à f . D’après le Théorème de Bézout nous avons δ ≤ d(d − 1)^{n−1} .

Alors il existe un réseau arithmétique N de taille (ndδL)^{O(1)} avec parmètres dans le corps des rationnels , qui représente au moins un point sur chaque composante connexe de l’hypersurface lisse et compacte de IR^{n}, definie par l’équation régulière f .

ii) Les hypothèses ci-dessus restant valables, soit δ^{∗} une borne supérieure des degrés réels de certaines variétés polaires associées à f (remarquons qu’on a δ^{∗} ≤ δ.

Alors il existe un réseau arithmétique N^{∗} de taille (ndδ^{∗}L)^{O(1)} avec parmètres dans le corps des rationnels , qui représente au moins un point sur chaque composante connexe de l’hypersurface lisse et compacte de IR^{n}, d’équation régulière f .

Ces résultats sont de complexités non–uniformes séquentielles et améliorent les estimations de la forme d^{O(n)} .

References

[GHMP,95].— M. Giusti, J. Heintz, J.E. Morais, L.M. Pardo “When polynomial equation systems can be “solved” fast?”. In Proc. 11th International Symposium Applied Algebra, Algebraic Algorithms and Error–Correcting Codes, AAECC–11, Paris 1995, G. Cohen, M.Giusti and T. Mora, eds., Springer LNCS 948 (1995) 205–231. [GHMMP,96].— M. Giusti, J. Heintz, J.E. Morais, J. Morgenstern, L.M. Pardo. “Straight–line programs in Geometric Elimination Theory”. to appear in J. of Pure and App. Algebra (1996). [GHHMMP,96].— M. Giusti, K, Hägele, J. Heintz, J.L. Montaña, J.E. Morais, L.M. Pardo.“Lower Bounds for Diophantine Approximations”. To Appear in Proc. MEGA’96, JPAA (1996).

4.15 Lower bounds for diophantine approximations.

J.E. Morais (Joint work with M. Giusti, J. Heintz, K. Hägele, J.L. Montaña, L.M. Pardo)

We introduce a subexponential algorithm for geometric solving of multivariate polynomial equation systems whose bit complexity depends mainly on intrinsic geometric invariants of the solution set.

From this algorithm, we derive a new procedure for the decision of consistency of polynomial equation systems whose bit complexity is also subexponential. As a byproduct, we analyze the division of a polynomial modulo a reduced complete intersection ideal and from this, we obtain an intrinsic lower bound for the logarithmic height of diophantine approximations to a given solution of a zero–dimensional polynomial equation system. This result represents a multivariate version of Liouville’s classical theorem on approximation of algebraic numbers by rationals.

A special feature of our procedures is their polynomial character with respect to the mentioned geometric invariants when instead of bit operations only arithmetic operations are counted at unit cost.

Technically our paper relies on the use of straight–line programs as a data structure for the encoding of polynomials, on a new symbolic application of Newton’s algorithm to the Implicit Function Theorem and on a special, basis independent trace formula for affine Gorenstein algebras.

4.16 Time–space trade–offs in algebraic complexity theory.

J.L. Montaña (Joint work with M. Aldaz, J. Heintz, G. Matera, L.M. Pardo)

Algebraic complexity deals with the inherent complexity of computing a set of rational functions. There are two main complexity measures: time and space. But rather than concentrate on time alone or space alone we study the time–space relationship for a selected family of polynomials which are already known as relevant from the point of view of time complexity were previously considered under the time complexity viewpoint. Call L(F) the non-scalar complexity and S(F) the space requirements for the evaluation of a given univariate polynomial F .

We stablish the following time–space tradeoffs for the product LS^{2} :

• “Almost all” complex univariate polynomials F of degree at most d a tradeoff LS^{2}(F) ≥ d/8 , and this bound is optimal because of Horner’s rule.

• We can also exhibit assymptotical trade–off lower bounds for concrete sequences (F_{d})_{d∈IN} of univariate polynomials as the following ones :

i) Polynomials with integer coefficients : A trade–off lower bound of order LS^{2}(F_{d}) ≥ Ω(d) holds where

F_{d} := ∑_{0≤i≤d} 2^{i!}X^{i}

ii) Polynomials given by their roots : A trade–off lower bound of order LS^{2}(F_{d}) ≥ Ω(d/log_{2}d) holds where

F_{d} := ∏_{0≤i≤d}(X − 2^{2^{i}})

iii) Polynomials with algebraic coefficients : A trade–off lower bound of order LS^{2}(F_{d}) ≥ Ω(d) holds where

F_{d} := ∑_{1≤i≤d} i^{1/i}Xi

iv) Polynomials with algebraic coefficients given by their roots : A trade–off lower bound of order LS^{2}(F_{d}) ≥ Ω(d/log_{2}d) holds where

F_{d} := ∏_{1≤i≤d}(X − j^{1/2})

• The following space requirements can be derived from the above bounds:

– Any algorithm of optimal non-scalar complexity for the evaluation of polynomials of the form i) or iii) requires space

S(F_{d}) ≥ Ω(d^{1/4})

– Any algorithm of optimal non-scalar complexity for the evaluation of polynomials of the form ii) or iv) requires space

S(F_{d}) ≥ Ω ((d/log_{2}d)^{1/4})

4.17 Rational plane curves and data structures: parametrization algorithms and applications.

J.R. Sendra

The aim of this talk is to show the basic ideas and main algorithmic difficulties in rational plane curve manipulations, and to analyze the feasibility of alternative data structures. Some problems related to projective plane curves as genus computation, implicitization, and parametrization of rational plane curves are considered, emphasizing on data structures, complexity and implementation aspects. Furthermore, special issues as optimal parametrizations, real curves and applications to offset curves (rationality analysis and construction of direct parametrization algorithms) are also treated.

More precisely, we start with the Max Noether classical algorithm for computing the genus and for parametrizing rational algebraic plane curves, and we show how the main algorithmic difficulties can be solved with symbolic techniques. The computing time analysis shows that genus computation and parametrization problem can be solved in polynomial time for curves without non-ordinary singularities. However, when a blowing up process is required, the worst case complexity may be exponential. The reason of this behaviour is that the depth of the neigborhood graph may not be bounded by a constant(we present an infinite family of rational plane curves {C_{k}} where the depth of the neigborhood graph is bounded by O(deg(C_{k})) ).

In addition we investigate the problem of computing optimal rational parametrizations, i.e. parametrizations having coefficients in an algebraic extension of least degree over the field of definition. Given an algebraic plane curve C of degree d over a ground field IK of characteristic zero, it is well known that if d is odd then C can be parametrized over IK , and if d is even then C can be parametrized over algebraic extension of IK of degree at most two. Using Hilbert-Hurwitz’s algorithm we show how this problem reduces to the problem of solving diophantine equations of genus zero, or equivalently, to the problem of computing optimal simple points on the curve. Furthermore, we present an improved version of the Hilbert-Hurwitz algorithm, based on the computation of families of two conjugate simple points on any rational plane curve, that avoids the O(d) birational transformation performs of the classical method.

Finally, we give some experimental values computing time for the algorithms described in the talk. These pratical examples reveal that the theoretical complexity bounds are too pessimistic for most cases (curves of degree 10 can be parametrized in a reasonable amount of time).

4.18 The Graeffe method in the multidimensional case and an application.

J. C. Yakoubson

We extend the classical Graeffe method to the multidimensional case. The application is to compute the distance of a point to an algebraic hypersurface.

5 Address of participants.

M. Aldaz  R. Alvarez Nodarse
Depto. de Matemáticas,  Depto. de Matemáticas
Univ. Pública de Navarra  Esc. Pol. Superior, Univ. Carlos III
Campus de Arrosadía,  C/ Butarque, 15
E-31.006 PAMPLONA, Spain  E-28911 Leganés, MADRID Spain
e–mail: mikaldaz@upna.es  e–mail: renato@dulcinea.uc3m.es

A. Campillo  B. Castaño
Depto. de Algebra y Geometría  Depto. de Matemáticas
F. Ciencias  Universidad de Alcalá
Univ. de Valladolid  Campus Universitario
Valladolid  Ctra. Madrid–Barcelona, Km. 33,600
Spain  E-28871 Alcalá de Henares, Madrid

Spain

e–mail: campillo@cpd.uva.es  e–mail : mtcastano@alcala.es

A. Colin  V. Cossart
Laboratoire GAGE, Centre de Mathématiques Laboratoire GAGE, Centre de Mathématiques
École Polytechnique (Univ. Paris X)  École Polytechnique (Univ. Paris X)
F-91228 Palaiseau cedex  F-91228 Palaiseau cedex
France  France
e–mail: colin@ariana.polytechnique.fr  e–mail : cossart@ariana.polytechnique.fr

J. P. Dedieu  J. von zur Gathen
LAO (Lab. Analyse et Optimisation)  Fachbereich 17 Mathematik-Informatik
Univ. Paul Sabatier  Universität-GH Paderborn
118, route de Narbonne  D-33095 Paderborn
F-31062 Toulouse Cedex  Germany
e–mail: dedieu@cict.fr  e–mail : gathen@math.uni-paderborn.de

K. Gerdes  M. Giusti
Laboratoire GAGE, Centre de Mathématiques Laboratoire GAGE, Centre de Mathématiques
École Polytechnique (Univ. Paris X)  École Polytechnique (Univ. Paris X)
F-91228 Palaiseau cedex  F-91228 Palaiseau cedex
France  France
e–mail: gerdes@ariana.polytechnique.fr  e–mail : giusti@ariana.polytechnique.fr

N. González Campos  M.J. González López
Depto. de Matemáticas, Est. y Comp.  Depto. de Matemáticas, Est. y Comp.
Fac. de Ciencias, Univ. de Cantabria  Fac. de Ciencias, Univ. de Cantabria
Avda. de los Castros, s/n  Avda. de los Castros, s/n
E-39071 Santander, Spain  E-39071 Santander, Spain
e–mail: gcampos@matesco.matsun1.unican.es  e–mail : glopez@matesco.matsun1.unican.es

L. González Vega  K. Hägele
Depto. de Matemáticas, Est. y Comp.  Depto. de Matemáticas, Est. y Comp.
Fac. de Ciencias, Univ. de Cantabria  Fac. de Ciencias, Univ. de Cantabria
Avda. de los Castros, s/n  Avda. de los Castros, s/n
E-39071 Santander, Spain  E-39071 Santander, Spain
e–mail: gvega@matesco.matsun1.unican.es  e–mail : haegele@matesco.matsun1.unican.es

J. Heintz  J.P. Henry
Depto. de Matemáticas, Est. y Comp.  Laboratoire GAGE, Centre de Mathématiques
Fac. de Ciencias, Univ. de Cantabria  École Polytechnique (Univ. Paris X)
Avda. de los Castros, s/n  F-91228 Palaiseau cedex
E-39071 Santander, Spain  France
e–mail: heintz@matesco.matsun1.unican.es  e–mail : henry@orphee.polytechnique.fr

F. Jamet  J. Kempe
Laboratoire GAGE, Centre de Mathématiques Laboratoire GAGE, Centre de Mathématiques
École Polytechnique (Univ. Paris X)  École Polytechnique (Univ. Paris X)
F-91228 Palaiseau cedex  F-91228 Palaiseau cedex
France  France
e–mail: jamet@ariana.polytechnique.fr  e–mail : kempe@ariana.polytechnique.fr

L. Kulesz  J. Llovet
UFR Mathématiques  Depto. de Matemáticas
Université Paris VII  Universidad de Alcalá
Couloir 45–55, 5éme étage  Campus Universitario
2, Place Jussieu  Ctra. Madrid–Barcelona, Km. 33,600
F-75251 Paris Cedex 05  E-28871 Alcalá de Henares, Madrid
France  Spain
e–mail: kulesz@mathp7.jussieu.fr  e–mail : illovet@alcala.es

R. Martínez  G. Mbakop
Dept. Automática, Electrónica e Inf. Indust.  Humbold–Universität
E. T. S. de Ingenieros Industriales  Institut für Informatik
Univ. Politécnica de Madrid  FB Mathematik
C. Jose Gutierrez Abascal,2  G. Unter den Linden, 6
E–28006, Madrid, Spain  D-10999 Berlin, Germany
e–mail: C0505001@ccupm.upm.es  e–mail : mbakop@mathematik.hu-berlin.de

J.L. Montaña  J.E. Morais
Depto. de Matemáticas,  Depto. de Matemáticas, Est. y Computación
Univ. Pública de Navarra  F. de Ciencias, Univ. Cantabria
Campus de Arrosadía,  Avda. Los Castros, s/n
E-31.006 PAMPLONA, Spain  E-39071 SANTANDER, Spain
e–mail: pepe@upna.es  e–mail: morais@matesco.matsun1.unican.es

J. Moulin Ollagnier  L.M. Pardo
Laboratoire GAGE, Centre de Mathématiques Depto. de Matemáticas, Est. y Computación
École Polytechnique (Univ. Paris X)  F. de Ciencias, Univ. Cantabria
F-91228 Palaiseau cedex  Avda. Los Castros, s/n
France  E-39071 SANTANDER, Spain
e–mail: moulin@gage.polytechnique.fr  e–mail : pardo@matesco.matsun1.unican.es

R. Sendra  J.A. Shih
Depto. de Matemáticas  Depto. de Algebra y Geometría
Universidad de Alcalá  Facultad de Ciencias
Ctra. Madrid–Barcelona, Km. 33,600  Univ. de Valladolid
E-28871 Alcalá de Henares, Madrid  Valladolid
Spain  Spain
e–mail: mtsendra@alcala.es  e–mail : shih@ariana.polytechnique.fr

J.C. Yakoubsohn LAO (Lab. Analyse et Optimisation) Univ. Paul Sabatier 118, route de Narbonne F-31062 Toulouse Cedex France e–mail: yak@cict.fr