Publications of the SPACES team

2004

Mohab Safey El Din and Eric Schost. Properness defects of projection functions and computation of at least one point in each connected component of a real algebraic set. Journal of Discrete and Computational Geometry, Sep 2004.

Computing at least one point in each connected component of a real algebraic set is a basic subroutine to decide emptiness of semi-algbraic sets, which is a fundamental algorithmic problem in effective real algebraic geometry. In this article, we propose a new algorithm for this task, which avoids a hypothesis of properness required in many of the previous methods. We show how studying the set of non-properness of a linear projection enables to detect connected components of a real algebraic set without critical points. Our algorithm is based on this result and its practical counterpoint, using the triangular representation of algebraic varieties. Our experiments show its efficiency on a family of examples.

Keywords: polynomial systems, real solutions

Richard Brent, Samuli Larvala, and Paul Zimmermann. A primitive trinomial of degree 6972593. Mathematics of Computation, Dec 2004.

The only primitive trinomial of degree 6972593 over (2) is x^6972593 + x^3037958 + 1 (apart from its reciprocal).

Keywords: irreducible polynomials, irreducible trinomials, primitive polynomials, primitive trinomials, mersenne exponents, mersenne numbers

David Defour, Guillaume Hanrot, Vincent Lefevre, Jean-Michel Muller, Nathalie Revol, and Paul Zimmermann. Proposal for a standardization of mathematical function implementation in floating-point arithmetic. Numerical Algorithms, Dec 2004.

Some aspects of what a standard for the implementation of the mathematical functions could be are presented. Firstly, the need for such a standard is motivated. Then the proposed standard is given. The question of roundings constitutes an important part of this paper: three levels are proposed, ranging from a level relatively easy to attain (with fixed maximal relative error) up to the best quality one, with correct rounding on the whole range of every function.We do not claim that we always suggest the right choices, or that we have thought about all relevant issues. The mere goal of this paper is to raise questions and to launch the discussion towards a standard.

Keywords: floating-point number, correct rounding, normalization, IEEE 754 standard

Guillaume Hanrot and Paul Zimmermann. A long note on mulders' short product. Journal of Symbolic Computation, Dec 2004.

The short product of two power series is the meaningful part of the product of these objects, i.e. _{i+j < n} a_ib_j x^i+j. In [?], Mulders gives an algorithm to compute a short product faster than the full product in the case of Karatsuba's multiplication [?]. This algorithm works by selecting a cutoff point k and performing a full k× k product and two (n-k)× (n-k) short products recursively. Mulders also gives a heuristically optimal cutoff point beta n. In this paper, we determine the optimal cutoff point in Mulders' algorithm. We also give a slightly more general description of Mulders' method.

Keywords: short product, odd-even product, mulders

Daniel Lazard. Injectivity of real rational mappings: The case of a mixture of two gaussian laws. Mathematics of Computation, Jun 2004.

Using methods from computer algebra, especially Gröbner bases, we study the application which maps the mixtures of two Gaussian laws of probability to their six first moments. It is proved that the mapping is injective, and thus that the parameters of the mixture may be recovered from the values of the moments. This method of proof may be applied to many physical problems where there are more measured variables than the state variables to be recovered.

Keywords: mixture of gaussian laws, application of computer algebra, rational mapping, method of the moments, identification of parameters

2003

Guillaume Hanrot, Joel Rivat, Gerald Tenenbaum, and Paul Zimmermann. Density results on floating-point invertible numbers. Theoretical Computer Science, 291(2):135-141, Jan 2003.

Let F_k denote the k-bit mantissa floating-point (FP) numbers. We prove a conjecture of J.-M. Muller according to which the proportion of numbers in F_k with no FP-reciprocal (for rounding to the nearest element) approaches (1)/(2)-(3)/(2)log(43 0.068476 89 as k->. We investigate a similar question for the inverse square root. )/()

Keywords: floating-point number, exact rounding

Vincent Lefèvre and Jean-Michel Muller. On-the-fly range reduction. Journal of VLSI Signal Processing-Systems for Signal, Image, and Video Technology, 33(1-2):31-35, Jan 2003.

In several cases, the input argument of an elementary function evaluation is given bit-serially, most significant bit first. We suggest a solution for performing the first step of the evaluation (namely, the range reduction) on the fly: the computation is overlapped with the reception of the input bits. This algorithm can be used for the trigonometric functions sin, cos, tan as well as for the exponential function.

Keywords: range reduction,elementary function

Dongming Wang. Automated generation of diagrams with maple and java. In N. Takayama M. Joswig, editor, Algebra, Geometry, and Software Systems, pages 277-287. Springer-Verlag, Berlin Heidelberg, Mar 2003.

This note shows how to draw diagrams automatically from the predicate specification of a given set of geometric relations among a set of points in the plane. It is done first in Maple by translating the geometric relations into polynomial equations, decomposing the obtained system of polynomials into irreducible representative triangular sets, and finding an adequate numerical solution from each triangular set. A Java class coding the solution and the polynomials in each triangular set is generated, compiled, and then executed with the main Java programs to draw a diagram. The whole process combining symbolic elimination in Maple with numerical computation, graphic drawing, and letter labelling in Java is fully automatic. The drawn diagrams may be animated and fine-tuned by mouse click and dragging and saved as PostScript files. We present the drawing method, discuss some techniques of implementation, and give several sample diagrams drawn by our program.

Keywords: diagram generation, geometric reasoning

Richard P. Brent, Samuli Larvala, and Paul Zimmermann. A fast algorithm for testing reducibility of trinomials mod 2 and some new primitive trinomials of degree 3021377. Mathematics of Computation, 72(243):1443-1452, Jul 2003.

The standard algorithm for testing reducibility of a trinomial of prime degree r over (2) requires 2r + O(1) bits of memory. We describe a new algorithm which requires only 3r/2 + O(1) bits of memory and significantly fewer memory references and bit-operations than the standard algorithm. If 2^r-1 is a Mersenne prime, then an irreducible trinomial of degree r is necessarily primitive. We give primitive trinomials for the Mersenne exponents r = 756839, 859433, and 3021377. % The results for r = 859433 extend and correct some computations of Kumada . The two results for r = 3021377 are primitive trinomials of the highest known degree.

Keywords: irreducible polynomials, irreductible trinomials, primitive polynomials, primitive trinomials, mersenne exponents, mersenne numbers, random number generators

Fabrice Rouillier and Paul Zimmermann. Efficient isolation of a polynomial real roots. Journal of Computational and Applied Mathematics, 162(1):33-50, 2003.

This paper revisits an algorithm isolating the real roots of a univariate polynomial using Descartes' rule of signs. It follows work of Vincent, Uspensky, Collins and Akritas, Johnson, Krandick. Our first contribution is a generic algorithm which enables one to describe all the known algorithms based on Descartes' rule of sign and the bissection strategy in a unified framework. Using that framework, a new algorithm is presented, which is optimal in terms of memory usage and as fast as both Collins and Akritas' algorithm and Krandick variant, independently of the input polynomial. From this new algorithm, we derive an adaptive semi-numerical version, using multi-precision interval arithmetic. We finally show that these critical optimizations have important consequences since our new algorithm still works with huge polynomials, including orthogonal polynomials of degree 1000 and more, which were out of reach of previous methods.

Keywords: univariate polynomial, real root, descartes' rule, uspensky

Dongming Wang. Geother 1.1: Handling and proving geometric theorems automatically. In Franz Winkler, editor, The Fourth International Workshop on Automated Deduction in Geometry - ADG 2002, Hagenberg, Austria. Franz Winkler, Springer-Verlag, Berlin Heidelberg, Sep 2003.

GEOTHER provides an environment for handling and proving theorems in geometry automatically. In this environment, geometric theorems are represented by means of predicate specifications. Several functions are implemented that allow one to translate the specification of a geometric theorem into English and Chinese statements, into algebraic expressions, and into logic formulas automatically. Geometric diagrams can also be drawn automatically from the predicate specification, and the drawn diagrams may be modified and animated with mouse click and dragging. Five algebraic provers based on Wu's method of characteristic sets, the Gröbner basis method, and other triangularization techniques are available for proving such theorems in elementary (and differential) geometry. Geometric meanings of the produced algebraic nondegeneracy conditions can be interpreted automatically, in most cases. PostScript and HTML files can be generated, also automatically, to document the manipulation and machine proof of the theorem. This paper presents these capabilities of GEOTHER, addresses some implementation issues, and reports on the performance of GEOTHER's algebraic provers.

Keywords: automated reasoning, geometry, theorem prover

Dongming Wang. A simple method for implicitizing rational curves and surfaces. Journal of Symbolic Computation, Dec 2003.

This paper presents a simple method for converting rational parametric equations of curves and surfaces into implicit equations. The method proceeds by writing out the implicit polynomial F of estimated degree with indeterminate coefficients u_i, substituting the rational expressions of the given parametric curve or surface into F to yield a rational expression g/h in the parameter s (or s and t), equating the coefficients of g with respect to s (and t) to 0 to generate a sparse, partially triangular system of linear equations in u_i with constant coefficients, and finally solving the linear system for u_i. If a nontrivial solution is found, then an implicit polynomial is obtained; otherwise, one repeats the same process by increasing the degree of F. Our experiments show that this simple method is efficient. It performs particularly well in the presence of base points and may detect the dependency of parameters incidentally.

Keywords: implicitization, rational surface, geometric design

Laurent Dupont, Daniel Lazard, Sylvain Lazard, and Sylvain Petitjean. Near-optimal parameterization of the intersection of quadrics. In 19th ACM Symposium on Computational Geometry - SoCG 2003, San Diego, USA, pages 246-255. ACM, Jun 2003.

In this paper, we present the first exact, robust and practical method for computing an explicit representation of the intersection of two arbitrary quadrics with rational coefficients. Combining results from the theory of quadratic forms, linear algebra and number theory, we show how to obtain parametric intersection curves that are near-optimal in the number and depth of radicals involved.

Keywords: intersection of quadrics

Falai Chen and Dongming Wang. Geometric Computation. World Scientific Publishing Co., Singapore New Jersey, Dec 2003.

The book comprises three closely related parts: the first is devoted mainly to curve and surface modeling, and contains one general survey on theoretical and practical applications of algebraic methods and three specialized surveys on surface blending, parametrization, and implicitization, followed by four research papers. The second part is concentrated on geometric reasoning, with one tutorial survey on Clifford algebra approaches, another on automated deduction in real geometry, and one research article. The last part is highlighted by a chapter that outlines a theory of real approximation, based on a generalization of the central idea of exact geometric computation. The book ends with one paper on A-resultant quotients and another on face recognition, which show how computer algebra and artificial intelligence meet geometry in the era of computation.

Keywords: computer aided geometric design, geometric reasoning, computer algebra

Dongming Wang. Elimination Practice: Software Tools and Applications. Imperial College Press, London,, Dec 2003.

The first half of the book presents the library Epsilon that has been built up for symbolic polynomial elimination and decomposition with (geometric) applications. It has 8 modules and contains more than 70 functions, which allow one to triangularize systems of multivariate (differential) polynomials, decompose polynomial systems into triangular systems of various kinds (regular, normal, simple, irreducible, or with projection property), decompose algebraic varieties into unmixed or irreducible subvarieties, decompose polynomial ideals into primary components, factorize polynomials over algebraic extension fields, solve systems of polynomial equations and inequations, and handle and prove geometric theorems automatically. The usefulness of the software tools are demonstrated in the second half of the book by a number of selected applications, ranging from qualitative analysis of differential equations in pure mathematics to geometry theorem discovering in automated reasoning and to surface blending and offsetting in computer-aided geometric design. These applications are illuminated with many examples and illustrations. The compact disk distributed with this book contains the entire Epsilon library with documentation, examples, and Maple worksheets.

Keywords: polynomial elimination, software, computer algebra, geometric reasoning

Dongming Wang. Selected Lectures in Symbolic Computation. Tsinghua University Press, Beijing, 2003.

Keywords: computer algebra and analysis, geometric reasoning, computer aided geometric design, real geometry

Dongming Wang. Implicitization and offsetting via regular systems. In Falai Chen and Dongming Wang, editors, Geometric Computation, chapter 5, pages 156-176. World Scientific, Singapore New Jersey, Dec 2003.

Given a geometric object defined by rational parametric equations, we show how to compute a disjunction of implicit equations and inequations that define exactly the same object by means of regular systems. The same technique is applied to the computation of quasi-offsets to algebraic curves and surfaces. Regular systems possess the projection property, are relatively easy to compute, and often have a compact form. Several examples are given to illustrate our approach based on the decomposition of polynomial systems into regular systems. A heuristic method is presented to simplify the output disjunction of polynomial equations and inequations.

Keywords: regular system, implicitization, offsetting

Damien Stehlé, Vincent Lefevre, and Paul Zimmermann. Worst cases and lattice reduction. In 16th IEEE Symposium on Computer Arithmetic 2003 - ARITH-16'03, Santiago de Compostela, Espagne, pages 142-147, Jun 2003.

We propose a new algorithm to find worst cases for correct rounding of an analytic function. We first reduce this problem to the Real Small Value Problem - i.e. for polynomials with real coefficients. Then we show that this second problem can be solved efficiently, by extending Coppersmith's work on the Integer Small Value Problem - for polynomials with integer coefficients - using lattice reduction. For floating-point numbers with a mantissa less than N, and a polynomial approximation of degree d, our algorithm finds all worst cases at distance < N^{(-d^2)/(2d+1)} from a machine number in time O(N^{(d+1)/(2d+1)+varepsilon}). For d=2, this improves on the O(N^{2/3+varepsilon}) complexity from Lefèvre's algorithm to O(N^{3/5+varepsilon}). We exhibit some new worst cases found using our algorithm, for double-extended and quadruple precision. For larger d, our algorithm can be used to check that there exist no worst cases at distance < N^-k in time O(N^{(1)/(2)+O((1)/(k))}).

Keywords: exact rounding, table maker's dilemma, worst case, ieee-754, lattice reduction, coppersmith's theorem

Daniel Augot, Magali Bardet, and Jean-Charles Faugère. Efficient decoding of (binary) the correction capacity of the code using gröbner bases. In IEEE International Symposium on Information Theory 2003 - ISIT'2003, Yokohama, Japon. IEEE, Jul 2003.

This paper revisits the topic of decoding cyclic codes with Gröbner bases. We introduce new algebraic systems, for which the Gröbner basis computation is easier. We show that formal decoding formulas are too huge to be useful, and that the most efficient technique seems to be to recompute a Gröbner basis for each word (online decoding). We use new Gröbner basis algorithms and ``trace preprocessing'' to gain in efficiency.

Keywords: decoding, cyclic codes, ideal theory, gröbner bases, error-locator polynomial, newton identities

Yan Gérard, Isabelle Debled-Rennesson, and Paul Zimmermann. A fast and elementary algorithm for digital plane recognition. Rapport de recherche, INRIA, Nov 2003.

A naive digital plane with integer coefficients is a subset of points (x,y,z) in Z^3 verifying a double inequality h <= ax+by+cz < h + max | a|,|b|, |c| where a,b,c and h are integer numbers. Given a finite subset of Z^3, a problem is to determine whether or not there exists a naive digital plane containing it. This question is rather classical in the field of digital geometry (also called discrete geometry). We suggest in this paper a new algorithm for solving it. It uses an original strategy of optimization in a set of triangular facets (called triangles). The code is short and elementary (less than 300 lines) and available on http://www.loria.fr/ debled/plane. Its theoretical complexity is bounded by O( n⁷) but its behavior is quasi-linear in practice.

Keywords: digital naive plane, chords set, triangular facet, linear programming

Mohab Safey El Din and Eric Schost. Polar varieties and computation of one point in each connected component of a smooth real algebraic set. In J.R. Sendra, editor, International Symposium on Symbolic and Algebraic Computation 2003 - ISSAC'2003, Philadelphie, USA, pages 224-231. ACM Press, Aug 2003.

Let f₁, ..., f_s be polynomials in [X₁, ..., X_n] that generate a radical ideal and let V be their complex zero-set. Suppose that V is smooth and equidimensional; then we show that computing suitable sections of the polar varieties associated to generic projections of V gives at least one point in each connected component of Vⁿ. We deduce an algorithm that extends that of Bank, Giusti, Heintz and Mbakop to non-compact situations. Its arithmetic complexity is polynomial in the complexity of evaluation of the input system, an intrinsic algebraic quantity and a combinatorial quantity.

Keywords: polynomial systems, real solutions, complexity

Colas Le Guernic. Résolution de systèmes d'égalités et d'inégalités polynomiales. Stage ens, ENS, Sep 2003.

Apres etude des methodes permettant de calculer un point par composante connexe de l'ensemble des solutions reelles des systemes d'equations polynomiales, nous montrons comment en deduire des algorithmes calculant un point par composante connexe de l'ensemble des solutions des systemes d'equations et d'inegalites larges. Nous montrons aussi que la complexite theorique des methodes que nous proposons est asymptotiquement optimale.

Keywords: polynomial systems, non-strict inequalities, real solutions

Vincent Lefèvre. Multiplication by an integer constant: Lower bounds on the code length. In 5th Conference on Real Numbers and Computers 2003 - RNC5, Lyon, France, pages 131-146, Sep 2003.

In this paper, we deal with code that performs a multiplication by a given integer constant using elementary operations, such as left shifts (i.e. multiplications by powers of two), additions and subtractions. Generating such a code can also be seen as a method to compress (or more generally encode) integers. We will discuss neither the way of generating code, nor the quality of this compression method, but this idea will here be used to find lower bounds on the code length, i.e. on the number of elementary operations.

Keywords: integer multiplication,addition chains,compression

Laurent Fousse and Paul Zimmermann. Accurate summation: Towards a simpler and formal proof. In 5th Conference on Real Numbers and Computers 2003 - RNC5, Lyon, France, Sep 2003.

This paper provides a simpler proof of the accurate summation algorithm proposed by Demmel and Hida. It also gives improved bounds in some cases, and examples showing that those new bounds are optimal. This simpler proof will be used to obtain a computer-checked proof of Demmel-Hida's algorithm.

Keywords: floating point summation, bounded error, formal proof

Emmanuel Thomé. Algorithmes de calcul de logarithmes discrets dans les corps finis. These d'universite, Ecole Polytechnique, May 2003.
[ .ps ]

Le calcul de logarithmes discrets est un problème central en cryptologie. Lorsqu'un algorithme sous-exponentiel pour résoudre ce problème existe, le cryptosystème concerné n'est pas nécessairement considéré comme disqualifié, et il convient d'actualiser avec soin l'état de l'art de la cryptanalyse. Les travaux de ce mémoire s'inscrivent dans cette optique. Nous décrivons en particulier comment nous avons atteint un record de calculs de logarithmes discrets: GF(2^607). Dans une première partie, nous exposons les différentes améliorations que nous avons apportées à l'algorithme de Coppersmith pour le calcul de logarithmes discrets en caractéristique 2. Ces améliorations ont rendu possible le record que nous avons atteint. La portée de ce calcul dépasse le simple cadre des corps finis, à cause de l'existence de la réduction MOV d'une part, et de la récente introduction des cryptosystèmes fondés sur l'identité. On s'intéresse plus en détail, dans une seconde partie du mémoire, au problème classique de la résolution d'un système linéaire creux défini sur un corps fini, porté aux limites de ce que la technologie (théorique et pratique) permet. Nous montrons comment une amélioration substantielle de l'algorithme de Wiedemann par blocs a rendu celui-ci compétitif pour la résolution d'un grand système linéaire creux sur GF(p). Une partie de ce mémoire est consacrée au point de vue de l'expérimentateur, grand utilisateur de moyens de calcul, de la surcharge de travail humain que cela impose, et des constatations que cette position amène.

Keywords: cryptology, discrete logarithms, algorithmics, linear algebra, coppersmith's algorithm, block wiedemann algorithm, distributed computation

Damien Stehlé. Breaking littlewood's cipher. Rapport de recherche, INRIA, Nov 2003.

In 1953, the celebrated mathematician John Edensor Littlewood proposed a stream cipher based on logarithm tables. Fifty years later, we propose the first analysis of his scheme. Littlewood suggests the idea of using real functions as tools to build cryptographic primitives. Even when considering modern security parameters, the original scheme can be broken by a simple attack based on differentiation. We generalise the scheme such that it resists this attack, but describe another attack which is derived from both polynomial approximation and Coppersmith's technique to find the small roots of modular multivariate polynomials. In contrast with these negative results we describe a candidate for a very efficient one-way function and present an open problem based on this work.

Keywords: littlewood's cipher, real functions, lattices, coppersmith's method

Richard Brent and Paul Zimmermann. Random number generators with period divisible by a mersenne prime. In Vipin Kumar Marina L. Gavrilova Chih Jeng Kenneth Tan Pierre l'Ecuyer, editor, International Conference on Computational Science and its Applications - ICCSA'2003, Montreal, Canada, volume 2667 of Lecture Notes in Computer Science, pages 1-10. Springer, May 2003.

Pseudo-random numbers with long periods and good statistical properties are often required for applications in computational finance. We consider the requirements for good uniform random number generators, and describe a class of generators whose period is a Mersenne prime or a small multiple of a Mersenne prime. These generators are based on ``almost primitive'' trinomials, that is trinomials having a large primitive factor. They enable very fast vector/parallel implementations with excellent statistical properties.

Keywords: random number, mersenne prime

Richard Brent and Paul Zimmermann. Algorithms for finding almost irreducible and almost primitive trinomials. In A. van der Poorten and A. Stein, editors, Primes and Misdemeanours: Lectures in Honour of the Sixtieth Birthday of Hugh Cowie Williams, Banff, Canada, May 2003.

Consider polynomials over (2). We describe efficient algorithms for finding trinomials with large irreducible (and possibly primitive) factors, and give examples of trinomials having a primitive factor of degree r for all Mersenne exponents r = 3 8 in the range 5 < r < 10⁷, although there is no irreducible trinomial of degree r. We also give trinomials with a primitive factor of degree r = 2^k for 3 <= k <= 12. These trinomials enable efficient representations of the finite field (2^r). We show how trinomials with large primitive factors can be used efficiently in applications where primitive trinomials would normally be used.

Keywords: irreducible trinomial, primitive trinomial

Paul Zimmermann. Arithmétique en précision arbitraire. Calculateurs Parallèles (Hermès), 2002.

Cet article dresse un panorama des différents algorithmes disponibles pour effectuer des calculs arithmétiques sur des nombres entiers ou flottants. Après un bref rappel des diverses représentations possibles pour les nombres entiers en précision arbitraire, les différents algorithmes connus de multiplication, division, racine carrée, pgcd, lecture et écriture sont présentés, ainsi que leur complexité et leur domaine d'application. Pour chaque opération, sont décrits l'algorithme % naïf << naïf >> et celui de meilleure complexité asymptotique connue, ainsi que des algorithmes intermédiaires de type % diviser pour régner << diviser pour régner >> ayant souvent une large plage d'utilisation. Pour les calculs flottants, outre les opérations de base (multiplication, division, racine carrée), des méthodes générales sont décrites pour le calcul des fonctions algébriques, élémentaires, hypergéométriques, holonomes et spéciales.

Keywords: integer, floating-point number, arbitrary precision

2002

Vincent Lefèvre. Multiplication by an integer constant: Lower bounds on the code length. Rapport de recherche, INRIA, Jul 2002.
[ .ps ]

The multiplication by a constant problem consists in generating code to perform a multiplication by an integer constant, using elementary operations, such as left shifts (multiplications by powers of two), additions and subtractions. This can also be seen as a method to compress (or more generally encode) integers. We will not discuss about the quality of this compression method, but this idea will be used to find lower bounds on the code length (number of elementary operations).

Keywords: integer multiplication,addition chain,compression

Laurent Dupont, Daniel Lazard, Sylvain Lazard, and Sylvain Petitjean. Towards the robust intersection of implicit quadrics. In J. Winkler and M. Niranjan, editors, Workshop on Uncertainty in Geometric Computations 2001, volume 704 of International Series in Engineering and Computer Science, chapter 5, pages 59-68. Kluwer Academic Publishers, Aug 2002.

We are interested in efficiently and robustly computing a parametric form of the intersection of two implicit quadrics with rational coefficients. Our method is similar in spirit to the general method introduced by J. Levin for computing an explicit representation of the intersection of two quadrics, but extends it in several directions. Combining results from the theory of quadratic forms, a projective formalism and new theorems characterizing the intersection of two quadratic surfaces, we show how to obtain parametric representations that are both ``simple'' (the size of the coefficients is small) and ``as rational as possible''.

Keywords: robustness, geometric computations, surface intersection, quadrics

Damien Stehlé, Vincent Lefèvre, and Paul Zimmermann. Worst cases and lattice reduction. Rapport de recherche, INRIA, Oct 2002.
[ .ps ]

Nous proposons un nouvel algorithme trouvant les pires cas pour l'arrondi d'une fonction mathématique, en calcul à virgule flottante. Dans un premier temps, nous réduisons ce problème à la recherche d'une petite valeur d'un polynôme à coefficients réels. Nous montrons ensuite que ce second problème peut être résolu efficacement, en étendant le travail de Coppersmith (utilisant la réduction des réseaux) sur la recherche de petites valeurs d'un polynôme à coefficients entiers. Pour des nombres flottants avec une mantisse bornée par N, et une approximation polynomiale de degré d, notre algorithme trouve tous les pires cas à distance inférieure à N^(-d²/(2d+1)) d'un nombre machine en temps O(N^((d+1)/(2d+1)+epsilon)). Pour d=2, cela améliore la complexité de l'algorithme de Lefèvre (O(N^(2/3+epsilon))) avec une complexité de O(N^(3/5+epsilon)). Nous exhibons de nouveaux pires cas trouvés avec notre algorithme, pour la double précision étendue et la quadruple précision. Pour un plus grand degré d, notre algorithme peut montrer qu'il n'existe pas de pire cas à distance inférieure à N^(-k) en temps O(N^(1/2+O(1/k))).

Keywords: exact rounding, table maker's dilemma, worst case, ieee-754 standard, lattice reduction, coppersmith's theorem

Yves Pétermann and Jean-Luc Rémy. On the cohen-olivier algorithm for computing zeta(s): error analysis in the real case for an arbitrary precision. Rapport de recherche, INRIA, 2002. soumis à publication.

We provide a complete error analysis of the Cohen-Olivier algorithm, for computing the zeta function, when the argument is real.

Keywords: error analysis, arbitrary precision, certified precision, riemann zeta-function

Yves Pétermann and Jean-Luc Rémy. Error analysis for an arbitrary precision in computing zeta(s) with the cohen-olivier algorithm : complete description of the real case and preliminary report on the general case. Rapport de recherche, INRIA, Dec 2002.

We provide a complete error analysis of the Cohen-Olivier algorithm, computing zeta(s), when the argument is real ; we indicate some further complexities which occur when the argument is complex.

Keywords: error analysis, arbitrary precision, certified precision, riemann zeta-function

Dongming Wang. Méthodes d'élimination avec applications. Science Press, Pékin, Aug 2002. Livre en chinois.

This book provides a systematic and uniform presentation of elimination methods for zero decomposition of polynomial systems. These methods can decompose any system of multivariate polynomials into triangular systems, regular systems, simple systems, triangular systems with the projection property, and irreducible triangular systems. The various triangularized systems differ in terms of theoretical properties, computational difficulties, and practical applicabilities. The book also covers the theory and techniques of resultants and Gröbner bases, addresses unmixed and irreducible decomposition of algebraic varieties and primary decomposition of polynomial ideals, and presents several applications of symbolic elimination methods, such as solving polynomial systems, proving geometric theorems, factorizing polynomials, and qualitative study of differential equations. Suitable as a text for a graduate or advanced undergraduate course in mathematics or computer science, this book offers an indispensable reference for students, researchers, and engineers interested in mathematical computation, computer algebra (software), and systems of algebraic equations.

Keywords: elimination, polynomial system, triangular set

Dongming Wang. Epsilon: A library of software tools for polynomial elimination. In N. Takayama A. M. Cohen, X.-S. Gao, editor, Proceedings of the First International Congress of Mathematical Software - ICMS 2002, Pékin, Chine, pages 379-389. World Scientific, Aug 2002.

This article presents a Maple library of functions for decomposing systems of multivariate polynomials into triangular systems of various kinds (regular, simple, or irreducible), with an application package for manipulating and proving geometric theorems.

Keywords: software, polynomial elimination, triangular decomposition, geometric reasoning

Yves Bertot, Nicolas Magaud, and Paul Zimmermann. A proof of gmp square root using the coq assistant. Rapport de recherche, INRIA, Jun 2002.
[ .ps ]

We present a formal proof (at the implementation level) of an efficient algorithm proposed in to compute square roots of arbitrarily large integers. This program, which is part of the GNU Multiple Precision Arithmetic Library (GMP), is completely proven within the system. Proofs are developed using the Correctness tool to deal with imperative features of the program. The formalization is rather large (more than 13000 lines) and requires some advanced techniques for proof management and reuse.

Keywords: arbitrary large number, formal method, gmp, coq

Harvey Dubner, Tony Forbes, Nik Lygeros, Michel Mizony, Harry Nelson, and Paul Zimmermann. Ten consecutive primes in arithmetic progression. Mathematics of Computation, 71(239):1323-1328, Apr 2002.

In 1967 the first set of 6 consecutive primes in arithmetic progression was found. In 1995 the first set of 7 consecutive primes in arithmetic progression was found. Between November, 1997 and March, 1998, we succeeded in finding sets of 8, 9 and 10 consecutive primes in arithmetic progression. This was made possible because of the increase in computer capability and availabiblity, and the ability to obtain computational help via the Internet. Although it is conjectured that there exist arbitrarily long sequences of consecutive primes in arithmetic progression, it is very likely that 10 primes will remain the record for a long time.

Keywords: consecutive primes, arithmetic progression

Paul Zimmermann. The elliptic curve method. In Encyclopedia of Information Security. Kluwer, Nov 2002.

Describes in two pages the history of ECM, how it works at high level, improvements to the method, and some applications.

Keywords: integer factorization, elliptic curve

Daniel Lazard. Discussion du nombre de solutions réelles d'un système dépendant de paramètres. In Mathématiques effectives, Poitiers, Sep 2002.

Nous décrivons un algorithme général pour déterminer, comme fonction des paramètres, le nombre de solutions réelles d'un système d'équations et d'inégalités polynomiales dépendant de paramètres. Cet algorithme a été appliqué à la résolution d'un difficile problème de mécanique célèste, qui sert ici à illustrer le fonctionnement mathématique de cet algorithme.

Keywords: polynomial system, parameters, real solution

Daniel Lazard. Central configurations of four gravitational masses with an axys of symmetry. In Workshop on Applications of Commutative Algebra - Catania 2002, Catania, Italie, Apr 2002.
[ .ps ]

This talk describes a common work with J.-C. Faugère. A central configuration of n masses under gravitational potential is a configuration such all accelerations are oriented toward the center of masses and proportional to the distance to this center. It follows that the plane central configurations are those that remain homothetic to themselves, with convenient initial velocities. For three masses, these configurations are well known as Lagrange positions. A well known conjecture is that the number of central configurations of n bodies is always finite when the masses are fixed. In this talk, we describe the number of central configurations of four masses in the plane, which have an axis of symmetry such symmetric masses are equal.

Keywords: central configurations, celestial mechanics, polynomial system, real solutions

Daniel Lazard. Central configurations of four gravitational masses with an axis of symmetry. In 8th International Conference on Applications of Computer Algebra - ACA 2002, Volos, Grèce, Jun 2002.
[ .ps ]

A central configuration of n masses under gravitational potential is a configuration such that all accelerations are oriented toward the center of masses and are proportional to the distance to this center. It follows that the plane central configurations are those that remain homothetic to themselves, with convenient initial velocities. For three masses these configurations are well known as those of Lagrange. A well known conjecture is that the number of central configurations of n bodies is always finite when the masses are fixed. In this talk, we describe the number of central configurations of four masses in the plane, which have an axis of symmetry. In this case symmetric masses are equal. In the case where none of the masses are on the axis (trapezoidal configuration), it is rather easy to show that for any value of the two masses, there is exactly one central configuration.

Keywords: central configurations, celestial mechanics, polynomial system, real solutions

Daniel Lazard. Solving quintics by radicals. In The Legacy of Niels Henrik Abel. Springer, Oct 2002.
[ .ps ]

A formula is given for solving by radicals any polynomial of degree 5 which is solvable by radicals. This formula is valid on any field of characteristic different from 2 and 5. The field extension which is generated by the radicals which appear in the result is always minimal, when only one root is produced, as well as when all roots are given. This formula has been implemented in Maple.

Keywords: solving by radicals, equation of degree five

Philippe Aubry, Fabrice Rouillier, and Mohab Safey El Din. Real solving for positive dimensional systems. Journal of Symbolic Computation, 34(6):543-560, Dec 2002.

Finding one point on each semi-algebraically connected component of a real algebraic variety, or at least deciding if such a variety is empty or not, is a fundamental problem of computational real algebraic geometry. Although numerous studies have been done on the subject, only a few number of efficient implementations exist. In this paper, we propose a new efficient and practical algorithm for computing such points. By studying the critical points of the restriction to the variety of the distance function to one well chosen point, we show how to provide a set of zero-dimensional systems whose zeros contain at least one point on each semi-algebraically connected component of the studied variety, without any assumption neither on the variety (smoothness or compactness for example) nor on the system of equations which define it. From the output of our algorithm, one can then apply, for each computed zero-dimensional system, any symbolic or numerical algorithm for counting or approximating the real solutions. We report some experiments using a set of pure exact methods. The practical efficiency of our method is due to the fact that we do not apply any infinitesimal deformations, unlike the existing methods based on a similar strategy.

Keywords: computer algebra, algebraic systems, real roots, connected components

Fabrice Rouillier. Computational problems related to positive polynomials. In Workshop on positive polynomials, Oberwolfach, Germany, Feb 2002.

Deciding if a semi-algebraic set is empty or not is critical for the study of problems related to positive polynomials. Only few implemented algorithms exists for this purpose : the Cylindrical Algebraic Decomposition (CAD) is the main one. Unfortunately, only small problems (with few variables and low degrees) can be solved using such methods. On the other hand, many algorithms with a good asymptotic complexity are proposed in the literature. Most of them are based on the so called Critical Points Method, for computing at least on point on each semi-algebraically connected component of a real algebraic set, used as a black box for deciding if a semi-algebraic set is empty or not. Unfortunately, due to the use of various tricks for keeping a good theoretical complexity (sum of squares, infinitesimal deformations, etc.), straightforward implementations of these algorithms are inefficient. We propose a new version of the Critical Points Method using the distance function to one (well chosen) point. Given any algebraic set V, we define an algebraic set C(V,A) that contains these critical points and a sub-algebraic variety of V. Our main result consists in proving that a good point A may be chosen so that C(V,A) is the disjoint union of a finite set of points and a sub-algebraic variety W of V with smaller dimension than V, without any restriction neither on the variety (do not need to be smooth or compact) nor on the set of polynomials used in the computations for the definition of V (for example, the generated ideal do not need to be prime). We are thus leaded to compute the isolated points of C(V,A) and to study, in the same way, the sub-variety W. We therefore obtain an algorithm without any infinitesimal deformation whose proof is simply based on the fact that the dimension of the studied varieties strictly decreases at each step. The limitations of such an algorithm are pointed out and solved (number of determinants) : we show how to use the theory of polynomial triangular sets to optimize the computations. We finally presents some practical experiments which illustrate the practical behavior of our algorithm. It shows the interest of our approach and justifies our choices.

Keywords: algebraic systems, real roots, connected components

Gabriel Dos Reis, Bernard Mourrain, Philippe Trébuchet, and Fabrice Rouillier. An environment for symbolic and numeric computation. In International Congress of Mathematical Software - ICMS'2002, Beijing, China. World Scientific, Aug 2002.

We describe the environment for symbolic and numeric computations, called SYNAPS (Symbolic and Numeric APplicationS) and developed in C++. Its aim is to provide a coherent platform integrating many of the nowadays freely available software in scientific computing. The approach taken here is inspired by the recent paradigm of software developments called active library. In this paper, we explain the design choices of the kernel and their impact on the development of generic and efficient codes for the treatment of algebraic objects, such as vectors, matrices, univariate and multivariate polynomials. Implementation details illustrate the performance of the approach. We describe the environment for symbolic and numeric computations, called SYNAPS (Symbolic and Numeric APplicationS) and developed in C++. Its aim is to provide a coherent platform integrating many of the nowadays freely available software in scientific computing. The approach taken here is inspired by the recent paradigm of software developments called active library. In this paper, we explain the design choices of the kernel and their impact on the development of generic and efficient codes for the treatment of algebraic objects, such as vectors, matrices, univariate and multivariate polynomials. Implementation details illustrate the performance of the approach.

Keywords: software integration, symbolic computations, numeric computations, applications

Nathalie Revol and Fabrice Rouillier. Motivations for an arbitrary precision interval arithmetic and the mpfi library. In SIAM Workshop on Validated Computing 2002, Toronto, Canada, May 2002.

MPFI is a library implementing interval arithmetic with arbitrary accuracy. It can be freely downloaded (including source code and documentation). It is written in C and is based on the MPFR library for arbitrary precision floating-point arithmetic, which is in turn built upon the GMP library. MPFR has been chosen because it provides outward rounding, even for the elementary functions, which is mandatory to implement interval arithmetic. An important issue in interval computation is computing in the large, i.e. getting tight enclosures for the range of a function over a large interval. However, this issue has no well established answer, and one common way to circumvent the problem consists in bisecting the input interval again and again, until the evaluation of the function upon each sub-part is tight enough. For some problems, such as roots approximations or optimization of a very flat function, splitting beyond the limits of usual (single or double) floating-point capacities reveals necessary in order to reach the required accuracy on the function evaluation.

Keywords: interval arithmetic, multiprecision

Solen Corvez and Fabrice Rouillier. Using computer algebra tools to classify serial manipulators. In Fourth International Workshop on Automated Deduction in Geometry - ADG 2002, Hagenberg, Austria , Sep 2002.

In this paper we present a classification of 3-revolute-jointed manipulators based on the cuspidal behaviour. It was shown in a previous work [?] that this ability to change posture without meeting a singularity is equivalent to the existence of a point in the workspace, such that a polynomial of degree four depending on the parameters of the manipulator and on the cartesian coordinates of the effector has a triple root. More precisely, from a partition of the parameters' space, such that in any connected component of this partition the number of triple roots is constant, we need to compute one sample point by cell, in order to have a full description, in terms of cuspidality, of the different possible configurations. This kind of work can be divided into two parts. First of all, thanks to Gröbner Bases computations, the goal is to obtain an algebraic set in the parameters' space describing the cuspidality behavior and then to compute a CAD adapted to this set. In order to simplify the problem, we use strongly the fact that a manipulator cannot be constructed with exact parameters, in other words, we are just interested in the generic solutions of our problem. This consideration leads us to work with triangular sets rather than with the global Gröbner Bases and to adapt the CAD of Collins as we will just take care of the cells of maximal dimension.

Keywords: groebner basis, cylindrical algebraic decomposition, triangular sets, serial manipulators, semialgebraic sets.

Mohab Safey El Din and Eric Schost. Properness defects of projections and computation of one point in each connected component of a real algebraic set. Rapport de recherche, INRIA, Oct 2002.

Computing at least one point in each connected component of a real algebraic set is a basic subroutine to decide emptiness of semi-algbraic sets, which is a fundamental algorithmic problem in effective real algebraic geometry. In this article, we propose a new algorithm for this task, which avoids a hypothesis of properness required in many of the previous methods. We show how studying the set of non-properness of a linear projection enables to detect connected components of a real algebraic set without critical points. Our algorithm is based on this result and its practical counterpoint, using the triangular representation of algebraic varieties. Our experiments show its efficiency on a family of examples.

Keywords: polynomial systems, real solutions

Guillaume Hanrot and Paul Zimmerman. A long note on mulders' short product. Rapport de recherche, INRIA, Nov 2002.
[ .ps ]

The short product of two power series is the meaningful part of the product of these objects, i.e., _i+j < n a_ib_j x^i+j. Mulders gives an algorithm to compute a short product faster than the full product in the case of Karatsuba's multiplication. This algorithm works by selecting a cutoff point k and performing a full kxk product and two (n-k)x(n-k) short products recursively. Mulders also gives an heuristically optimal cutoff point beta n. In this paper, we determine the optimal cutoff point in Mulders' algorithm. We also give a slightly more general description of Mulders' method.

Keywords: short product, power series, karatsuba multiplication

Fabrice Rouillier. Outils pour l'etude des zéros réels de systèmes algébriques. In Journées de Géométrie Algorithmique - JGA'02, Obernai, France, Oct 2002.

Nous présentons quelques algorithmes performants, utilisant principalement du calcul exact, pour l'étude des zéros réels des systèmes algébriques. Ce type d'algorithmes, dont la sortie est complètement certifiée, permet d'obtenir des résultats souvant impossible à établir par des méthodes purement numériques : existance de zéros réels, nombre de zéros réels, isolation des coordonnées des solutions, multiplicités. Ceci sera présenté sur la base d'un ou deux exemples pratiques, issus de problèmes académiques ou industriels. Les outils (et rappels théoriques nécessaires) seront introduits un à un au cours de résolution de ces exemples.

Keywords: computer algebra, algebraic systems, applications

Fabrice Rouillier. Real solving and parallel robots. In Workshop on Computations and Applications in RAAG 2002, Santander, Spain, Jun 2002.

We describe the general characteristics of both families of known robots (serial and parallel) as well as the main problems requiring the use of results of real algebraic geometry more or less sophisticated. We detail then the use which is at present done by certain algorithms of exact calculation for the settling of complex and powerful machine tools and we review some existing software solutions. We show in particular how these solutions allow to diagnose and to finalize a system of command for machine tools on base of parallel mechanisms.

Keywords: robots, computer algebra

Fabrice Rouillier. Outils pour l'étude des zéros réels de systèmes algébriques. In Colloque Mathématiques Effectives , Poitiers, France, Sep 2002.

Nous faisons un tour d'horizon de quelques méthodes formelles utilisées et implantées pour la résolution des systèmes algébriques. Nous nous attardons sur le cas des systèmes de dimension positive en décrivant des méthodes basées sur l'étude des points critiques de fonctions bien choisies.

Keywords: algebraic systems, computer algebra , real roots

Solen Corvez and Fabrice Rouillier. Using computer algebra tools to classify serial cuspidal manipulators. Rapport de recherche, INRIA, Dec 2002.

In this paper we present a classification of 3-revolute-jointed manipulators based on the cuspidal behaviour. It was shown in a previous work that this ability to change posture without meeting a singularity is equivalent to the existence of a point in the workspace, such that a polynomial of degree four depending on the parameters of the manipulator and on the cartesian coordinates of the effector has a triple root. More precisely, from a partition of the parameters' space, such that in any connected component of this partition the number of triple roots is constant, we need to compute one sample point by cell, in order to have a full description, in terms of cuspidality, of the different possible configurations.

Keywords: computer algebra, gröbner bases, cylindrical algebraic decomposition, triangular sets, serial robots, semi-algebraic sets

Daniel Augot, Magali Bardet, and Jean-Charles Faugere. Efficient decoding of (binary) cyclic codes beyond the correction capacity of the code using gröbner bases. Rapport de recherche, LORIA, Nov 2002. Version partielle soumise a ISIT 2003 Japan.

The problem of decoding cyclic codes can be rewritten into an algebraic system of equations, whose solutions are closely related to the error that occured. Extensive work has been done previously, where it has been shown that the computation of a Gröbner basis of this algebraic system enables to decode up to the true minimum distance. The Gröbner basis computation can be done either as a preprocessing (formal decoding), with the parameters taken as variables, or for each word to be decoded (online decoding), with the parameters computed from the word and substituted into the system. For the formal decoding, it has been shown that decoding formulas for the coefficients of the locator polynomial are obtained from the formal Gröbner basis. Unfortunately, it becomes quickly impossible to compute this formal Gröbner basis even for codes of small length. Motivated by the problem of decoding quadratic residue (QR) codes, for which no general decoding algorithm is known, we improve on several points. First we introduce modified systems, without high degree equations, for which the Gröbner basis computation is easier. This enables to compute the formal Gröbner basis for longer codes. We show on the example of the [41,21,9] QR code that the formulas become quickly of large size, thus being useless for decoding. This indicates that the effort on the algebraic decoding of cyclic codes by formulas hits a wall. The other approach (online decoding) is more efficient from a computational point of view. Using general compilation methods for systems with parameters, we improve the efficiency of the computation. Many examples are given (for BCH codes of length 75, 511, for QR codes of length 41, 73, 89, 113 and for a code of length 75 which does not belong to a known class of codes). This method for decoding cyclic codes with Gröbner basis works for any cyclic codes, is automatic and enables to decode beyond the true minimum distance.

Keywords: decoding , cyclic codes , ideal theory , gröbner bases , error-locator polynomial , newton identities

Jean-Charles Faugere. A new efficient algorithm for computing gröbner bases without reduction to zero f5. In International Symposium on Symbolic and Algebraic Computation Symposium - ISSAC 2002, Villeneuve d'Ascq, France, Jul 2002.

This paper introduces a new efficient algorithm for computing Gröbner bases. We replace the Buchberger criteria by an optimal criteria. We give a proof that the resulting algorithm (called F5) generates no useless critical pairs if the input is a regular sequence. This a new result by itself but a first implementation of the algorithm F_5 shows that it is also very efficient in practice: for instance previously untractable problems can be solved (cyclic 10). In practice for most examples there is no reduction to zero. We illustrate this algorithm by one detailed example.

Keywords: groebner

Jean-Charles Faugere. A new efficient algorithm for computing gröbner bases without reduction to zero. In Eighth Rhine Workshop on Computer Algebra -RWCA 2002 , Mannheim, Germany, Mar 2002.

Goal of F5 Computing Gröbner bases of (f₁,...,f_m): Buchberger algorithm or F4 Open issue: remove useless computations. 90% of the time is spent in computing zero -> a more powerful criterion to remove useless critical pairs. Goal of F5: theoretical and practical answer.

Keywords: groebner

Jean-Charles Faugere. A new efficient algorithm for computing gröbner bases without reduction to zero. In Workshop on application of Groebner Bases 2002, Catania, Spain, Apr 2002.

Goal of F5 Computing Gröbner bases of (f₁,...,f_m): Buchberger algorithm or F4 Open issue: remove useless computations. 90% of the time is spent in computing zero -> a more powerful criterion to remove useless critical pairs. Goal of F5: theoretical and practical answer.

Keywords: groebner

Jean-Charles Faugere. Gröbner bases and application to hfe. In YACC 2002 - Conference on Cryptography, Porquerolles, France, Jun 2002.

HFE (Hidden Fields Equations) is a public key cryptosystem using polynomial operations over finite fields. It has been proposed by Jacques Patarin at Eurocrypt 96 following the ideas of Matsumoto and Imai. It has long been regarded as a very promising cryptosystem because it can be used to produce signatures as short as 128, 100 and even 80 bits. HFE gives the shortest (unbroken) signatures known except with the recent McEliece signature scheme. To study HFE it is necessary to study and to solve polynomial system of equations. One of the most efficient tool for solving algebraic system is Gröbner bases (Buchberger). In this conference we present 3 new results:

• we discribe briefly a new efficient algorithm for computing V called F₅/2. This algorithm is several order of magnitude faster than any other algorithms (at least 500 times faster than the Singular program for instance).
• For a fixed value d of the univariate polynomial we report the CPU time taken by the F₅/2 algorithm to solve the HFE problem. For instance, when d=96, we found experimentally that the time for solving the HFE problem is only n⁸. We were able to solve the first HFE Challenge (n=16,d=96) in 96 hours.
• We present accurate theoretical results concerning the complexity of solving a random system in GF(2). The complexity of computing a Gröbner basis of a random system of n equations of degree 2 in n variables is essentially equivalent to solve a N× N matrix with

  N 1.5 (1.35ⁿ)/(sqrt(n)) when n->

  This show that that HFE system are not random system. The difference with a random system for the challenge 1 can be detected after 12 hours.

Keywords: groebner, hfe, crypto

Jean-Charles Faugere. Classification of all planar central configurations of n bodies with equal masses in the case of the logarithmic potential and n<8. In 8th International Conference on Applications of Computer Algebra - ACA 2002 , Volos, Grèce, Jun 2002.

First we give a new way to model the problem using complex numbers and elementary symetric functions. The new equations can be solved by hand for N=4 and several infinite families can be found using this new formulation. By using Groebner bases computations we are able to make a complete classification of the solutions for N=4,5,6,7. For N<8 there is a always a finite number of solutions and a symmetry.

Keywords: groebner, n body problem, logarithmic potential

Jean-Charles Faugere, Milena Hering, and Jeff Phan. The membrane inclusions curvature equations. Advances in Applied Mathematics, Oct 2002.

We examine a system of equations arising in biophysics whose solutions are believed to represent the stable positions of N conical proteins embedded in a cell membrane. Symmetry considerations motivate two equivalent refomulations of the system which allow the complete classification of solutions for small N<13. The occurrence of regular geometric patterns in these solutions suggests considering a simpler system, which leads to the detection of solutions for larger N up to 280. We use the most recent techniques of Groebner bases computation for solving polynomial systems of equations.

Keywords: stable position of proteins, groebner

Absolali Basiri, Andrea Enge, Jean-Charles Faugere, and Nicolas Gurel. The arithmetic of jacobian groups of superelliptic cubics. Mathematics of Computation, Dec 2002. Existe en Rapport INRIA RR-4618.

We present two algorithms for the arithmetic of cubic curves with a totally ramified prime at infinity. The first algorithm, inspired by Cantor's reduction for hyperelliptic curves, is easily implemented with a few lines of code, making use of a polynomial arithmetic package. We prove explicit reducedness criteria for superelliptic curves of genus 3 and 4, which show the correctness of the algorithm. The second approach, quite general in nature and applicable to further classes of curves, uses the FGLM algorithm for switching between Gröbner bases for different orderings. Carrying out the computations symbolically, we obtain explicit reduction formulae in terms of the input data.

Keywords: superelliptic curve, c_ab curve, jacobian, arihmetic, gröbner basis

Manuel Benito, Wolfgang Creyaufmueller, Juan Luis Varona, and Paul Zimmermann. Aliquot sequence 3630 ends after reaching 100 digits. Experimental Mathematics, 11(2):201-206, Nov 2002.

In this paper we present a new computational record: the aliquot sequence starting at 3630 converges to 1 after reaching a hundred decimal digits. Also, we show the current status of all the aliquot sequences starting with a number under 10000. In particular, we have reached at least 112 digits for the so-called ``Lehmer five sequences'', and 101 digits for the ``Godwin twelve sequences''. Finally, we give a summary showing the number of aliquot sequences of unknown end starting with a number <= 10⁶.

Keywords: aliquot sequences, sum of divisors, perfect number, amicable pair, sociable numbers, aliquot cycles

Paul Zimmermann. Symbolic computation: Recent progress and new frontiers. In International Symposium on Scientific Computing, Computer Arithmetic, and Validated Numerics (SCAN), Sep 2002.
[ .ps ]

Symbolic computation and computer algebra systems are usually known to be either very slow, or memory expensive. However, some specific symbolic computation problems have received in the last years new algorithmic solutions, which enabled to push further the limits of what is doable within a reasonable amount of time and space. Some noticeable examples are polynomial factorisation, lattice reduction, Groebner basis computation. We will present a few such algorithms, together with a state-of-the-art of what problems computer algebra systems can (or cannot) solve, and for each problem what the current frontiers are.

Keywords: computer algebra, recent result

Daniel Lazard. Mélange de deux lois gaussiennes; systèmes sur-déterminés dépendant de paramètres approchés. In Journees LNF, Liens Calcul Numerique-Calcul Formel, Toulouse, France, Dec 2002.
[ .ps ]

On montre que l'application, qui associe les moments d'ordres jusqu'à six à un mélange de lois gaussiennes, est injective. Cela permet d'envisager une résolution stable du système d'équations sur-déterminé, qui définit les paramètres du mélange à partir des valeurs mesurées de moments.

Keywords: overdetermined system, approximate parameters, gaussian law

Yves Bertot, Nicolas Magaud, and Paul Zimmermann. A proof of GMP square root. Journal of Automated Reasoning, 29(3-4):225-252, Dec 2002. Special Issue on Automating and Mechanising Mathematics: In honour of N.G. de Bruijn.

We present a formal proof (at the implementation level) of an efficient algorithm proposed by Paul Zimmermann [?] to compute square roots of arbitrary large integers. This program, which is part of the GNU Multiple Precision Arithmetic Library (GMP) is completely proven within the Coq system. Proofs are developed using the Correctness tool to deal with imperative features of the program. The formalization is rather large (more than 13000 lines) and requires some advanced techniques for proof management and reuse.

Keywords: formal proof, coq, arithmetic, gnu mp

2001

Laurent Dupont, Sylvain Lazard, Sylvain Petitjean, and Daniel Lazard. Towards the robust intersection of implicit quadrics. In Workshop on Uncertainty in Geometric Computations, Sheffield, UK, Jul 2001.

We are interested in efficiently and robustly computing a parametric form of the intersection of two implicit quadrics with rational coefficients. Our method is similar in spirit to the general method introduced by J. Levin for computing an explicit representation of the intersection of two quadrics, but extends it in several directions. Combining results from the theory of quadratic forms, a projective formalism and new theorems characterizing the intersection of two quadratic surfaces, we show how to obtain parametric representations that are both ``simple'' (the size of the coefficients is small) and ``as rational as possible''.

Keywords: robustness of geometric computations, quadric surface intersection

Guillaume Hanrot and Francois Morain. Solvability by radicals from an algorithmic point of view. In Bernard Mourrain, editor, International Symposium on Symbolic and Algebraic Computation - ISSAC'2001, London, Ontario, Canada. ACM, Jul 2001.

Any textbook on Galois theory contains a proof that a polynomial equation with solvable Galois group can be solved by radicals. From a practical point of view, we need to find suitable representations of the group and the roots of the polynomial. We first reduce the problem to that of cyclic extensions of prime degree and then work out the radicals, using the work of Girstmair. We give numerical examples of Abelian and non-Abelian solvable equations and apply the general framework to the construction of Hilbert Class fields of imaginary quadratic fields.

Keywords: galois theory, algebraic equations, solving by radicals

Fabrice Rouillier and Paul Zimmermann. Efficient isolation of a polynomial real roots. Rapport de recherche, INRIA, Feb 2001.

This paper gives new results for the isolation of real roots of a univariate polynomial using Descartes' rule of signs, following work of Vincent, Uspensky, Collins and Akritas, Johnson, Krandick. The first contribution is a generic algorithm which enables one to describe all the existing strategies in a unified framework. Using that framework, a new algorithm is presented, which is optimal in terms of memory usage, while doing no more computations than other algorithms based on Descartes' rule of signs. We show that these critical optimizations have important consequences by proposing a full efficient solution for isolating the real roots of univariate polynomials or zero-dimensional polynomial systems with integral coefficients. We then adapt the algorithm for a use with multi-precision floating point arithmetics providing an adaptative method that give an exact result in every situation.

Keywords: polynomial, real root, uspensky's algorithm, descartes' rule

Karim Belabas, Guillaume Hanrot, and Paul Zimmermann. Tuning and generalizing van hoeij's algorithm. Rapport de recherche, INRIA, Feb 2001.

Recently, van Hoeij's published a new algorithm for factoring polynomials over the rational integers [?]. This algorithms rests on the same principle as Berlekamp-Zassenhaus [?], but uses lattice basis reduction to improve drastically on the recombination phase. The efficiency of the LLL algorithm is very dependent on fine tuning; in this paper, we present such tuning to achieve better performance. Simultaneously, we describe a generalization of van Hoeij's algorithm to factor polynomials over number fields.

Keywords: polynomial, factorization, lll algorithm

Guillaume Hanrot, Natarajan Saradha, and Tarlok Shorey. Almost perfect powers in consecutive integers. Acta Arithmetica, 99(1):13-25, 2001.

We study a generalized version of a theorem of Erdos and Selfridge on when a product of consecutive integers is a pure power.

Keywords: perfect powers, diophantine equations, thue equations

Yuri Bilu, Guillaume Hanrot, and Paul Voutier. Existence of primitive divisors of lucas and lehmer numbers. Journal Für die reine und angewandte Mathematik, 539:75-122, Oct 2001.

We prove that for n>30, every n-th Lucas and Lehmer number has a primitive divisor. This allows us to list all Lucas and Lehmer numbers without a primitive divisor.

Keywords: lucas sequences, primitive divisors, thue equations

Vincent Lefèvre and Jean-Michel Muller. Worst cases for correct rounding of the elementary functions in double precision. In Neil Burgess and Luigi Ciminiera, editors, 15th IEEE Symposium on Computer Arithmetic - ARITH 2001, Vail, Colorado, pages 111-118, Jun 2001.

We give the results of a four-year search for the worst cases for correct rounding of the major elementary functions in double precision floating-point arithmetic. These results allow the design of reasonably fast routines that will compute these functions with correct rounding, at least in some interval, for any of the four rounding modes specified by the IEEE-754 standard. They will also allow one to easily test libraries that are claimed to provide correctly rounded functions.

Keywords: table maker's dilemma, elementary function, computer arithmetic, correct rounding, floating-point arithmetic

Vincent Lefèvre. Multiplication by an integer constant. Rapport de recherche, INRIA, May 2001.

We present and compare various algorithms, including a new one, allowing to perform multiplications by integer constants using elementary operations. Such algorithms are useful, as they occur in several problems, such as the Toom-Cook-like algorithms to multiply large multiple-precision integers, the approximate computation of consecutive values of a polynomial, and the generation of integer multiplications by compilers.

Keywords: multiplication, addition chain

Luc Rolland. Introduction to algebraic methods for solving the forward kinematics problem of parallel robots applied to high throughput and high accuracy. In Third European-Asian Congress on Mecatronics, Besançon, France. Laboratoire Automatique de Besançon, Oct 2001.

After the recent success of parallel robots in flight simulation and material handling, engineers have introduced them in the fields of machine-tools and medicine. These machines ought to fulfill high accuracy and fast throughput requirements such as encountered in milling and surgery. Inasmuch, this poses serious challenges to engineers. In fact, they were left without satisfactory and effective methods to solve all kinematics problems. Hence, these are essential in the realization of significative computer tools to measure, model and simulate the robot behavior in order to help the designer, the user and the technician to insure that the robot shall successfully accomplish a specified task. The use of perfomant algebra tools applied to geometry in a computer algebra environment opens the way to all exact solutions to the kinematics problem by the implementation of perfomant tools such as algebraic system representation, Groebner bases, rational univariate representation RUR and real root isolation.

Keywords: parallel robot, kinematics, geometry, algebra, exact and symbolic computations, groebner basis, variable isolation, rational univariate representation, real roots, path planning

Luc Rolland. Méthodes algébriques pour la résolution du modèle géométrique de robots parallèles, applications à haute cadence et grande précision. In Quatrièmes Journées du Pôle Microrobotique, Lyon, France. Laboratoire d'Automatique Industrielle, Jul 2001.

Suite aux récents succès de manipulateurs parallèles en simulation de vol et manutention industrielle, ces mécanismes apparaissent de plus en plus dans les domaines de la machine-outil et la médecine. Or, leur conception et mise au point doit répondre à des exigences sévères de haute précision et de grande cadence tels que ceux rencontrés en usinage ou chirurgie; Or, cela pose de sérieux défis aux ingénieurs. En effet, ils restaient toujours sans méthodes satisfaisantes et efficaces pour résoudre tous les modèles cinématiques. Bref, elles sont essentielles à l'élaboration d'outils informatiques qui peuvent modéliser, simuler et mesurer le comportement du robot et ces outils serviront d'aide au concepteur, à l'utilisateur et au technicien pour mettre au point un robot qui accomplit une tâche avec succès. Grâce à de nouveaux algorithmes, l'utilisation de l'algèbre en géométrie dans un environnement de calcul exact et formel permet d'envisager toutes les solutions exactes en proposant des outils performants tels que les modélisations algébriques, les bases de Gröbner, la représentation univariée rationnelle et des techniques de calcul des racines de polynôme.

Keywords: parallel robot, kinematics, geometry, algebra, exact methods, assembly modes, singularités, task study

David Daney and Ioannis Z. Emiris. Robust parallel robot calibration with partial information. In IEEE International Conference on Robotics and Automation - ICRA'2001, Corée, Séoul, May 2001.

A new algorithm for calibrating Gough platforms is proposed. It requires internal sensor measurements and only the position information provided by external sensors. It removes the need to measure orientation, which is intricate and error-prone, by algebraic elimination. This approach, relying on resultants and dialytic elimination, produces an equivalent, yet simpler, set of equations. Numerical simulation compares existing techniques using partial information to our method, which proves to be significantly more robust, without compromising accuracy: it reduces initial error in pose determination by 99% and 80-98%, in two sets of experiments with realistic conditions. We compare different choices for the measured configurations and show the relevance of configurations at the workspace's boundary. This increases reliability by avoiding to use any random measured configurations.

Keywords: parallel robot, calibration, sparse elimination

David Daney and Ioannis Z. Emiris. Variable elimination for reliable parallel robot calibration. In Franck C. Park and Cornel C. Iurascu, editors, In 2nd Workshop on Computational Kinematics - CK'2001, Seoul, Korea. School of Mechanical and Aerospace Engineering, May 2001.

We study overconstrained polynomial systems from an algebraic and numerical perspective in order to improve the accuracy and reliability of Gough platform calibration. By elimination theory, we may limit ourselves to measuring only the position information by external sensors, besides internal sensor measurements. Measuring orientation, which is intricate and error-prone, becomes unnecessary. A planar analogue is used to formally develop the technique and analyze observability by means of the Jacobian. Several experiments are used to compare the existing alternatives with partial information to our approach, by numerical simulation. It is shown that our method significantly improves robustness without compromising accuracy, especially when the measured configurations lie at the workspace's boundary.

Keywords: parallel robot, calibration, sparse elimination, planar robot

Jean-Charles Faugere. Finding all the solutions of cyclic 9 using groebner basis techniques. In Shirayanagi and Yokoyama, editors, Fifth Asian Symposium on Computer Mathematics - ASCM'2001, Matsuyama, Japan, volume 9 of Lecture Notes on Computing, pages 1-12. World Scientific, Sep 2001.

We show how computer algebra methods based on Groebner basis computation and implemented in the program FGb enable us to compute all the solution of the Cyclic 9 problem a previously untractable problem. There are one type of infinite solutions of dimension two and 6156 isolated points without multiplicities.

Keywords: groebner, cyclic, decomposition

Daniel Lazard. On the specification for solvers of polynomial systems. In 5th Asian Symposium on Computer Mathematics - ASCM 2001, Matsuyama, Japon, volume 9 of Lecture Notes Series on Computing, pages 66 - 75. World Scientific, Sep 2001.
[ .ps ]

In this paper, the main different methods for solving polynomial systems ( es, triangular sets, ...) are compared on an example coming from geometry. It is shown that these methods may be combined for automatically studying the number of admissible real solutions of a polynomial system depending on parameters; this study provides as output a description of this number as a function of the parameters.

Keywords: computer algebra, symbolic computation, algebraic computation, polynomial system solving, polynomial equation, polynomial inéquation, geometry, triangle, gröbner basis, triangular set

Mohab Safey El Din. Résolution réelle des systèmes polynomiaux de dimension positive. Thèse d'université, Université Paris 6, Jan 2001.
[ .ps ]

Cette these traite de l'etude des solutions reelles des systemes polynomiaux en dimension positive. Plus precisement, il s'agit de determiner au moins un point par composante connexe sur une variete algebrique reelle. Dans le cadre des methodes etudiees, ceci peut etre vu comme une etape du processus de resolution des systemes d'equations et d'inegalites polynomiales, et du probleme d'elimination des quantificateurs. Les travaux de ma these consistent a remanier algorithmiquement une methode (methode des points critiques) pour obtenir des algorithmes efficaces en pratique donnant au moins un point par composante connexe sur une variete algebrique reelle. Le principe de cette methode est connu : il s'agit de calculer les points critiques d'une application reguliere atteignant des extrema locaux sur chaque composante connexe de la variete. L'objectif est de ramener le probleme a l'etude de systemes de dimension zero pour lesquels il existe des algorithmes de resolution efficaces. La complexite theorique des algorithmes relevant de cette methode est simplement exponentielle en le nombre de variables (tant en terme de nombre d'operations qu'en terme de taille de la sortie), ce qui est optimal pour un probleme de cette nature. Neanmoins les techniques mises en oeuvre (deformations infinitesimales, somme de carres) pour atteindre cette complexite ne permettent pas d'obtenir des implantations efficaces. Dans ma these, une premiere etude (menee avec F. Rouillier et M.-F. Roy) traite du cas des hypersurfaces (une seule equation). Dans les cas sans singularites, le calcul des points critiques de la fonction distance a un point permet de trouver au moins un point par composante connexe sur la variete etudiee. Dans les cas ou l'hypersurface contient une infinite de singularites, une seule deformation infinitesimale est requise pour se ramener au cas precedent. Des outils de calcul efficace sont donnes pour la resolution de tels systemes zero-dimensionnels a coefficients infinitesimaux. Les implantations de l'algorithme obtenu sont plus efficaces que les meilleures implantations de l'algorithme le plus connu pour resoudre ce type de probleme (la decomposition cylindrique algebrique). Dans les cas singuliers, des progres restent a faire. Une deuxieme etude (avec P. Aubry et F. Rouillier) traite du cas des systemes polynomiaux (plusieurs equations). Les singularites sont isolees et etudiees en tant que varietes algebriques dont la dimension est strictement inferieure a celle de la variete initiale, tandis que les points reguliers de la variete, et qui sont critiques pour la fonction distance a un point, sont calcules. L'algorithme obtenu etudie iterativement des varietes equi-dimensionnelles dont la dimension decroit a chaque pas. Ses implantations sont plus efficaces de plusieurs ordres de grandeur que les meilleures implantations de l'algorithme de decomposition cylindrique algebrique. Dans un troisieme temps, ces algorithmes sont significativement ameliores. En tirant profit d'informations sur la projection de la variete, l'etude d'ensembles constructibles est integre au processus de resolution. Une deformation infinitesimale est necessaire et les outils de calcul developpes precedemment sont utilises a bon escient dans ce cadre. Enfin, les outils et implantations developpes sont utilises pour resoudre de maniere automatisee un cas du probleme d'interpolation de Birkhoff qui restait un probleme ouvert.

Keywords: algebraic systems, real solutions, critical points

Daniel Lazard. Systèmes d'équations algébriques et robots parallèles. In P. Rives et D. Meizel, editor, Journées nationales de la recherche en robotique - JNRR'2001, Presu'île de Giens, France. P. Rives et D. Meizel, INRIA, Sophia Antipolis, Oct 2001.

Les robots parallèles font intervenir des systèmes d'équations polynomiales difficiles, qui ont longtemps été au delà des possibilités des logiciels de résolution. Dans cet article, on montre comment les progrès de ces logiciels ont régulièrement été suivis de progrès dans la connaissance de ces robots : Il y a quelques années les logiciels ne permettaient que de compter le nombre de solutions complexes. Aujourd'hui, ils permettent de calculer rapidement toutes les solutions réelles, avec une précision garantie, ce qui permet la simulation et la commande de haute précision de robots effectivement construits.

Keywords: parallel robot, system of algebraic equations

Paul Zimmermann. De l'algorithmique à l'arithmétique via le calcul formel. Habilitation à diriger des recherches, Université Henri Poincaré - Nancy 1, Nov 2001.

Ce mémoire présente mes travaux de recherche de 1988 à 2001, travaux effectués d'abord à l'INRIA Rocquencourt au sein du projet Algo (1988 à 1992), puis à l'INRIA Lorraine et au LORIA dans les projets Euréca (1993 à 1997), PolKA (1998 à 2000), et Spaces (2001). Au niveau thématique, on peut distinguer grosso modo trois phases : une première période allant de 1988 à 1992 où j'ai surtout travaillé sur l'analyse d'algorithmes et la génération aléatoire, une seconde période de 1993 à 1997 où je me suis investi dans le calcul formel et les algorithmes sous-jacents, enfin une troisième période depuis 1998 où je me suis intéressé aux problèmes d'arithmétique exacte en précision arbitraire.

Keywords: algorithms, computer algebra, arithmetics

Vincent Lefèvre. Multiplication par une constante. Réseaux et Systèmes Répartis, Calculateurs Parallèles, 13(3):465-484, 2001.

Nous présentons et comparons divers algorithmes, dont un nouveau, permettant d'effectuer des multiplications par des constantes entières à l'aide d'opérations élémentaires. De tels algorithmes sont utiles, car les multiplications par des constantes interviennent dans de nombreux problèmes. Ces algorithmes peuvent être utilisés directement par le programmeur (par exemple en multiprécision, pour les algorithmes du style Toom-Cook afin de multiplier des entiers à grande précision et pour le calcul approché de valeurs consécutives d'un polynôme) ou bien par les compilateurs afin de générer des multiplications entières pour certains processeurs.

Keywords: multiplication

Philippe Aubry and Dongming Wang. Reasoning about surfaces using differential zero and ideal decomposition. In D. Wang J. Richter-Gebert, editor, Third International Workshop on Automated Deduction in Geometry - ADG'2000, Zurich, Switzerland, volume 2061 of Lecture Notes in Artificial Intelligence, pages 154-174, Berlin Heidelberg, 2001. J. Richter-Gebert, D. Wang, Springer-Verlag.

This paper presents methods for zero and ideal decomposition of partial differential polynomial systems and the application of these methods and their implementations to deal with problems from the local theory of surfaces. We show how to prove known geometric theorems and to derive unknown relations automatically. In particular, an algebraic relation between the first and the second fundamental coefficients in a very compact form has been derived, which is more general and has smaller degree than a relation discovered previously by Z. Li. Moreover, we provide symmetric expressions for Li's relation and clarify his statement. Some examples of theorem proving and computational difficulties encountered in our experiments are also discussed.

Keywords: automatic reasoning, differential algebra, differential geometry, triangular decomposition

Dongming Wang. Elimination Methods. Texts and Monographs in Symbolic Computation. Springer-Verlag, Wien New York, Jan 2001.

This book provides a systematic and uniform presentation of elimination methods and the underlying theories, along the central line of decomposing arbitrary systems of polynomials into triangular systems of various kinds. Highlighting methods based on triangular sets, the book also covers the theory and techniques of resultants and Gröbner bases. The methods and their efficiency are illustrated by fully worked out examples and their applications to selected problems such as from polynomial ideal theory, automated theorem proving in geometry and the qualitative study of differential equations. The reader will find the formally described algorithms ready for immediate implementation and applicable to many other problems. Suitable as a graduate text, this book offers an indispensable reference for everyone interested in mathematical computation, computer algebra (software), and systems of algebraic equations.

Keywords: mathematical computation, computer algebra, algebraic geometry

Xiaorong Hou, Hongbo Li, Dongming Wang, and Lu Yang. ``russian killer'' no. 2: A challenging geometric theorem with human and machine proofs. The Mathematical Intelligencer, 23(1):9-15, Jan 2001.

This article presents one human proof and three machine proofs of a challenging geometric theorem that gives a beautiful representation of the area of an arbitrary quadrilateral in terms of its four sides and four internal angles. These proofs demonstrate the power, capability and features of automated deduction methods and tools, which reduce qualitative difficulty to quantitative complexity versus traditional methods with individual ingenious ideas, for mathematical theorem proving. The present case study not only results in four probably new proofs of a hard theorem but also contributes to understanding the significance of developing effective algorithms and software tools for automated theorem proving in mathematics using advanced computing technology.

Keywords: machine proof, geometric theorem, automated proving

Dongming Wang. A generalized algorithm for computing characteristic sets. In K. Shirayanagi and K. Yokoyama, editors, The Fifth Asian Symposium on Computer Mathematics - ASCM'2001, Matsuyama, Japan, volume 9 of Lecture Notes Series on Computing, pages 165-174, Singapore, Sep 2001. World Scientific Publishing Co.

We generalize Wu-Ritt's algorithm for the computation of characteristic sets by means of one-step pseudo-reduction instead of pseudo-division. This generalization results in a new algorithm which, with optimal selection of reductors and heuristic generation of S-polynomials, may speed up the computation considerably and produce simpler output for large problems. Examples and experiments are provided to show the performance of our new algorithm.

Keywords: characteristic set, wu-ritt algorithm

Dongming Wang and Dongdai Lin. A method for multivariate polynomial factorization over successive algebraic extension fields. In D. Lin W. Li and Y. Yu, editors, Mathematics and Mathematics-Mechanization, pages 138-172. Shandong Education Publishing House, Jinan, May 2001.

We present a method for factorizing multivariate polynomials over algebraic fields obtained from successive extensions of the field of rational numbers. The basic idea underlying this method is the reduction of polynomial factorization over algebraic extension fields to the factorization over the rational number field via linear transformation and the computation of characteristic sets with respect to a proper variable ordering. The factors over the algebraic extension fields are finally determined via greatest-common-divisor computation. This method has been implemented in the Maple system. Preliminary experiments show that it is rather efficient. We give timing statistics in Maple 4.3 on 40 test examples taken from the literature or randomly generated. For all those examples to which the Maple built-in algorithm is applicable, our algorithm is always faster.

Keywords: polynomial factorization, algebraic extension field, characteristic set

Dongming Wang. Geometric reasoning with geometric algebra. In E. Bayro-Corrochano and G. Sobczyk, editors, Advances in Geometric Algebra with Applications, pages 87-111. Birkhäuser, Boston, Apr 2001.

This chapter starts with an introduction to Clifford algebra for Euclidean geometry and shows how geometric theorems can be proved automatically in the Clifford algebra formalism. A short review of available approaches is given and examples are provided. We report an experiment which demonstrates how identities in Clifford algebra can be effectively proved using the induction principle with heuristic simplification.

Keywords: clifford algebra, geometric theorem proving, automated proof of identity, induction principle

Dongming Wang. Elimination theory, methods, and practice. In W. Li D. Lin and Y. Yu, editors, Mathematics and Mathematics-Mechanization, pages 91-137. Shandong Education Publishing House, Jinan, 2001.

This article gives an informal account of the theory, algorithms, software tools, and applications of polynomial elimination. It covers most of the important ideas, methods, and up-to-date advances on classical resultants, sparse elimination, triangular/characteristic sets, Gröbner bases, matrix eigenproblems, and homotopy continuation. A selected bibliography is provided for the reader to access the rich literature on the subject.

Keywords:

Daniel Lazard. Résolution numérique des systèmes algébriques par des techniques exactes : application à la mécanique céleste. In SMAI, editor, Congrès national de mathématiques appliquées et industrielles, SMAI 2001, Pompadour, France, pages 159-160. SMAI, May 2001.

Les techniques de fésolution des systèmes d'équations polynomiales par des méthodes exactes ont fait récemment de tels progrès, qu'elles permettent d'obtenir des résultats qui sont totalement inaccessibles aux méthodes numériques, notamment à cause des erreurs d'arrondi. Nous présentons une application à la mécanique céleste qui montre les possibilités maintenant ouvertes par les techniques du clacul formel.

Keywords: algebraic system, central configuration, celestial mechanics, symbolic computation

Jürgen Richter-Gebert and Dongming Wang. Automated Deduction in Geometry - ADG 2000 Revised Papers, volume 2061 of Lecture Notes in Artificial Intelligence. Springer, Sep 2001.

With a standard program committee and a pre-review process, the Third International Workshop on Automated Deduction in Geometry (ADG 2000) held in Zurich, Switzerland, September 25-27, 2000 was made more formal than the previous ADG ?96 (Toulouse, September 1996) and ADG ?98 (Beijing, August 1998). The workshop program featured two invited talks given by Christoph M. Hoffmann and Jürgen Bokowski, one open session talk by Wen-tsün Wu, 18 regular presentations, and 7 short communications, together with software demonstrations (see http://calfor.lip6.fr/ wang/ADG2000/). Some of the most recent and significant research developments on geometric deduction were reported and reviewed, and the workshop was well focused at a high scientific level. Fifteen contributions (out of the 18 regular presentations selected by the program committee from 31 submissions) and 2 invited papers were chosen for publication in these proceedings. These papers were all formally refereed and most of them underwent a double review-revision process. We hope that this volume meets the usual standard of international conference proceedings, represents the current state of the art of ADG, and will become a valuable reference for researchers, practitioners, software engineers, educators, and students in many ADG-related areas from mathematics to CAGD and geometric modeling. ADG 2000 was hosted by the Department of Computer Science, ETH Zurich.

Keywords:

Daniel Lazard. Optimality of the parameterization of quadrics and their intersections. In Journées de cloture Visi3D et CoSTIC, Paris, France, Dec 2001.
[ .ps ]

It is shown that any intersection of two quadrics may be pamareterized with at most two square roots by components (except when the intersection consists in 4 colinear lines), and we provide an algorithm for computing which is always optimal in the number of square roots which are involved. However, in some cases, this optimality needs a sub-algorithm for finding a ratiaonal point on a conic, if any.

Keywords: parameterization, quadric surfaces, intersection

Daniel Lazard. Solving systems of algebraic equations. ACM SIGSAM Bulletin, 35(3):11-37, Sep 2001.

Let f1,&hellip;,fk be k multivariate polynomials which have a finite number of common zeros in the algebraic closure of the ground field, counting the common zeros at infinity. An algorithm is given and proved which reduces the computations of these zeros to the resolution of a single univariate equation whose degree is the number of common zeros. This algorithm gives the whole algebraic and geometric structure of the set of zeros (multiplicities, conjugate zeros,&hellip;). When all the polynomials have the same degree, the complexity of this algorithm is polynomial relative to the generic number of solutions. Translation by Michael Abramson of the paper Résolution des systèmes d'équations algébriques. Theoretical Computer Sciences, 15 (1981), 77-110.

Keywords: polynomial system, algebraic system

Jean-Charles Faugere. Solving polynomial systems. algorithms and applications. In Computer Algebra in Applications to Integrable Systems , Cambridge, England, Nov 2001.

This talk presents new algorithms for solving polynomial systems and in particular two new efficient algorithms for computing Gröbner bases. To avoid as much as possible intermediate computation, the F4 algorithm computes successive truncated Gröbner bases and replaces the classical polynomial reduction found in the Buchberger algorithm by the simultaneous reduction of several polynomials. This powerful reduction mechanism is achieved by means of a symbolic precomputation and by extensive use of sparse linear algebra methods. A second algorithm, called F5, eliminate the Buchberger criteria so that there is no reduction to zero during the computation when the input system is a regular sequence. In a second part of the talk we review different applications solved by these algorithms/programs (Robotic, Cryptography, N body problem, Coding theory, ...).

Keywords: groebner, applications

2000

Richard P. Brent, Samuli Larvala, and Paul Zimmermann. A fast algorithm for testing irreducibility of trinomials mod 2. Rapport de recherche, Oxford University Computing Laboratory, Dec 2000.

The standard algorithm for testing reducibility of a trinomial of prime % this assumption avoids GCD test for divisors of the degree degree r over (2) requires 2r + O(1) bits of memory and Theta(r²) bit-operations. We describe an algorithm which requires only 3r/2 + O(1) bits of memory and significantly fewer bit-operations than the standard algorithm. Using the algorithm, we have found 18 new irreducible trinomials of degree r in the range 100151 <= r <= 700057. If r is a Mersenne exponent (i.e. 2^r-1 is a Mersenne prime), then an irreducible trinomial is primitive. Primitive trinomials are of interest because they can be used to give pseudo-random number generators with period at least 2^r-1. We give examples of primitive trinomials for r = 756839, 859433, and 3021377. The three results for r = 756839 are new. The results for r = 859433 extend and correct some computations of Kumada [Math. Comp. 69 (2000), 811-814]. The two results for r = 3021377 are primitive trinomials of the highest known degree.

Keywords: irreducible polynomial, primitive polynomial, trinomial

Daniel Lazard. Calcul formel : tendances et progrès récents. Technique et Science Informatique, 19(1-2-3):325-333, Jan 2000.

Les tendances de l'évolution des logiciels de calcul formel sont présentées, telles qu'elles sont ressenties par l'auteur à l'aube de l'an 2000. Deux points sont paticulièrement développés : La multiplications des logiciels spécialisés performants et la résolution des systèmes d'équations polynomiales, où des progrès remarquables sont en cours.

Keywords: computer algebra, symbolic computation, algebraic computation, polynomial system solving, polynomial equations, polynomial inéquations

Daniel Lazard. Resolution of polynomial systems. In 4th Asian Symposium on Computer Mathematics - ASCM 2000, Chiang Mai, Thailand, volume 8 of Lecture Notes Series on Computing, pages 1 - 8. World Scientific, Dec 2000.
[ .ps ]

In this talk, the state of the art of solving polynomial system by algebraic methods is sketched, and the main directions where future work is needed are indicated. Emphasis is given on input-output specification rather than on technical algorithmic aspects

Keywords: computer algebra, symbolic computation, algebraic computation, polynomial system solving, polynomial equation, polynomial inéquation, gröbner basis, triangular set

Henri Lombardi, Marie-Françoise Roy, and Mohab Safey El Din. New structure theorems for subresultants. Journal of symbolic computation, 29(4-5):663-689, May 2000.

We give a new structure theorem for subresultants precising their gap structure and derive from it a new algorithm for computing them. If d is a bound on the degrees and t a bound on the bitsize of the minors extracted from Sylvester matrix, our algorithm has O(d2) arithmetic operations and size of intermediate computations 2 t. The key idea is to precise the relations between the successive Sylvester matrix of A and B in one hand and of A and XB on the other hand, using the notion of G-remainder we introduce. We also compare our new algorithm with another algorithm with the same characteristics given by L. Ducos.

Keywords: subresultants, sylvester matrix

Fabrice Rouillier, Marie-Françoise Roy, and Mohab Safey El Din. Finding at least one point in each connected component of a real algebraic set defined by a single equation. Journal of Complexity, 16(4):716-750, Dec 2000.

Deciding efficiently the emptiness of a real algebraic set defined by a single equation is a fundamental problem of computational real algebraic geometry. We propose an algorithm for this test. We find, when the algebraic set is non empty, at least one point on each semi-algebraically connected component. The problem is reduced to deciding the existence of real critical points of the distance function and computing them.

Keywords: real solutions hypersurfaces infinitesimals

Fabrice Rouillier, Mohab Safey El Din, and Eric Schost. Solving the birkhoff interpolation problem via the critical point method: an experimental study. In Third International Workshop on Automated Deduction in Geometry - ADG'2000, Zurich, Switzerland, 2000.

Following the work of Gonzalez-Vega, this paper is devoted to show how to use recent algorithmic tools of computational real algebraic geometry to solve the Birkhoff Interpolation Problem. We recall and partly improve two algorithms to find at least one point in each connected component of a real algebraic set defined by a single equation or a polynomial system of equations, both based on the computation of the critical points of a distance function. These algorithms are used to solve the Birkhoff Interpolation Problem in a case which was known to be an open problem.

Keywords: birkhoff interpolation problem, real solutions, singularities, infinitesimals

Philippe Aubry, Fabrice Rouillier, and Mohab Safey El Din. Real solving for positive dimensional systems. Rapport de recherche, INRIA, Sep 2000.

Finding one point on each semi-algebraically connected component of a real algebraic variety, or at least deciding if such a variety is empty or not, is a fundamental problem of computational real algebraic geometry. Even though numerous studies have been done on the subject, only a few number of efficient implementations exists. In this paper, we propose a new efficient and practical algorithm for computing such points. By studying the critical points of the restriction to the variety of the distance function to one well chosen point, we show how to provide a set of zero-dimensional systems whose zeroes contain at least one point on each semi-algebraically connected component of the studied variety, without any assumption neither on the variety (smoothness or compactness for example) nor on the system of equations that define it. Once such a result is computed, one can then apply, for each computed zero-dimensional system, any symbolic or numerical algorithm for counting or approximating the solutions. We have made experiments using a set of pure exact methods. The practical efficiency of our method is due to the fact that we do not apply any infinitesimal deformations, conversely to the existing methods based on similar strategy.

Keywords: real solutions, algebraic systems

Philippe Aubry and Annick Valibouze. Using galois ideals for computing relative resolvents. Journal of Symbolic Computation, 30(6):635-651, Dec 2000. Special Issue on Algorithmic Galois Theory.

In this paper we show that some ideals which occur in Galois theory are generated by triangular sets of polynomials. This geometric property seems important for the development of symbolic methods in Galois theory. It may and should be exploited in order to obtain more efficient algorithms, and it enables us to present a new algebraic method for computing relative resolvents which works with any polynomial invariant.

Keywords: resolvent, galois theory, galois ideal, ideal of relations

Xiao-Shan Gao and Dongming Wang. Computer Mathematics - Proceedings of the Fourth Asian Symposium - ASCM'2000, volume 8 of Lecture Notes Series on Computing. World Scientific Publishing Co., Singapore, Dec 2000.

This volume contains selected papers presented at the Fourth Asian Symposium on Computer Mathematics. 39 peer-reviewed original contributions together with full papers and extended abstracts by the four invited speakers, G H Gonnet, D Lazard, W McCune, and W-T Wu, cover some of the most recent and significant advances in computer mathematics, including algebraic, symbolic, numeric, and geometric computation, automated mathematical reasoning, mathematical software, and computer-aided geometric design. Researchers, teachers, students, and engineers interested in doing mathematics using computers will find this volume good reading and a valuable reference.

Keywords: symbolic, algebraic, and geometric computation, automated reasoning, computational geometry/cagd, computational differential equations, software design and implementation, graph algorithms

Xiaorong Hou and Dongming Wang. Subresultants with the bézout matrix. In X.-S. Gao and D. Wang, editors, The Fourth Asian Symposium on Computer Mathematics, Chiang Mai, Thailand, volume 8 of Lecture Notes Series on Computing, pages 19-28, Singapore, Dec 2000. World Scientific Publishing Co.

Subresultants are defined usually by means of subdeterminants of the Sylvester matrix. This paper gives an explicit and simple representation of the subresultants in terms of subdeterminants of the Bézout matrix and thus provides an alternative definition for subresultants. The representation and the lower dimensionality of the Bézout matrix lead to an effective technique for computing subresultant chains using determinant evaluation. Our preliminary experiments show that this technique is computationally superior to the standard technique based on pseudo-division for certain classes of polynomials.

Keywords: subresultant, bézout matrix, determinant evaluation