ABSTRACTS BOOKLET

Workshop on

Applications of Commutative Algebra

April 3-6, 2002

Dipartimento di Matematica e Informatica

Catania - ITALY

Scientific Committee: Giuseppa Carrà Ferro, University of Catania Italy Lorenzo Robbiano, University of Genova Italy Carlo Traverso, University of Pisa Italy

CoCoA 5

John Abbott DIMA - Dipartimento di Matematica Via Dodecaneso, 35 16146 Genova - ITALY abbott@dima.unige.it

Over the last fifteen years the CoCoA project has been dedicated to producing a useful computational tool for researchers studying polynomial systems. The CoCoA program is more focused and specialized than the general purpose computer algebra systems, and consequently is able to benefit from a dedicated and uncompromised approach. CoCoA also places great emphasis on being easy and natural to use via its own programming language.

Lately the CoCoA project has entered a new phase: completely rebuilding and restructuring the program (as a separate library and interface) using the language C++, and employing more modern algorithms where available. The aims of the new version include offering better flexibility and performance while retaining the simplicity of use for which CoCoA has become widely appreciated. We present some of the main aspects of this new incarnation: CoCoA 5.

ALGEBRA AND GEOMETRY OF MOLECULAR CAD

Chandrajit Bajaj Center for Computational Visualization Computer Sciences & TICAM University of Texas at Austin http://www.cs.utexas.edu/ bajaj bajaj@cs.utexas.edu

The high combinatorial complexity and flexibility of macromolecules and associated potential fields, makes for interesting computational challenges in developing an interactive computer aided molecular design and visualization system. In this talk I shall focus on multiresolution geometry data structures which while volumetric, allow for smooth algebraic spline approximations of molecular surfaces, corresponding to level sets of electron density. Support is also provided for interrogative topological, and metric querying of molecular shape and associated electrostatic / interaction energy potential fields, via differential or integral calculations of the spline representation. The collection of data structures and algorithms prove useful for a range of rapid molecular manipulations, including quantifying shape complementarity, structural analysis, molecular docking, and animation.

NEIGHBORHOODS OF ALGEBRAIC DIFFERENTIAL EQUATIONS

Giuseppa Carrà Ferro Dipartimento di Matematica e Informatica Viale A. Doria, 6 95125 Catania - ITALY carra@dmi.unict.it

Many data are often ”uncertain” if either they come from physical measurements and observations or they are the output of numerical computations. So a real number is represented approximately because of the limited number of digits. For all these reasons it is growing up the necessity of combining methods in computer algebra and numerical analysis. If we know that a value is not exact we represent it by an interval. The notions of neighborhood of a polynomial are discussed in [10], [11] and in [9]. Here the notion of neighborhood of a linear ordinary differential equation with constant coefficients is introduced as in [5] and it is extended to the more general case of algebraic differential equations. If we know that the coefficients have limited accuracy, we work with the family of the differential operators having coefficients within a given tolerance instead of working with a single differential operator: all these operators form the differential operator neighborhood. In this context it is introduced the notion of pseudo-integral of a differential equation as the integral of a differential equation in its neighborhood. Furthermore the notion of differential resultant is used in order to know the relations between the integrals of a linear ordinary differential equation with constant coefficients and the integrals of a linear ordinary differential equation in its neighborhood. The same tool can be used in more general cases. For our experiments we use two computer algebra packages: Maple 6 [6] and Mathematica 4.1 [12]. The use of Mathematica 4.1 is essential because this package works with interval arithmetic [1,7].

\underline{References}

[1] Alefeld G., Claudio D. : The basic properties of interval = arithmetic, its software realization and some applications., Computer and Structures, 67, 1998, pp. 3-8

[2] Berkovich, L.M., Tsirulik, V.G.: Differential Resultants and some of their Applications., Differential Equations, Plenum Publ. Corp., Vol. 22 N. 55 (1986) pp. 750-757

[3] Carrà Ferro G.: A Resultant Theory for Systems of Linear = Partial Differential Equations., In:Ibragimov, N.H. Mahomed, F. M. (eds.) Proceeedings of Modern Group Analysis V (Lie Groups and their Applications, Vol. 1), pp. 47-55, Istambul: 1994

[4] Carrà Ferro G.: A Resultant Theory for the Systems of Two = Ordinary Algebraic Differential Equations., In: AAECC , Vol. 8 N. 6, Springer, 1997, pp. 539-560

[5] Carrà Ferro G. and Marotta V.: Neigborhoods of an Ordinary = Linear Differential Equation., In: Computer Algebra in Scientific Computation (Eds. V.G. Ganzha, E.W. Mayr, E.V. Vorozhtsov) Springer 2001, pp. 107-122

[6] Geddes K.O., Monogan M.B., Heal K.M., Labahn G., Vorkoetter S.M. = McCarron S.: MAPLE 6, Programming Guide, Waterloo Maple Inc., Canada 2000

[7] Hansen E.: Global Optimization using Interval Analysis., Marcel = Dekker Inc, New York-Basel-Hong Kong, 1992

[8] Macaulay F.S.: The Algebraic Theory of Modular Systems, Cambridge: Proc. Cambridge Univ. Press 1916

[9] Marotta V.: Resultants and Neighborhoods of a Polynomial., preprint 2000

[10] Stetter H.J.: Polynomial with Coefficients of Limited Accuracy., In: Computer Algebra in Scientific Computing (Eds. V.G.Ganzha, E.W.Mayr, E.V.Vorozhtsov), Springer, 1999, pp. 409-430

[11] Stetter H.J.: Nearest Polynomial with a Given Zero., preprint, to appear in SIGSAM Bulletin, 2000

[12] S. Wolfram: The Mathematica Book, 4th ed., Wolfram Media, = Cambridge University Press, 1999

A LIBRARY FOR POLYNOMIAL ARITHMETIC

Fabrizio Caruso RISC-Linz, J. Kepler University Linz, A-4040 Austria fcaruso@risc.uni-linz.ac.at

A C++ library has been developed which implements the basic polynomial operations (addition, multiplication, exponentiation) and some operations specially tailored for polynomial expressions related to some combinatorial problems.

The library treats different types of polynomials: dense univariate, sparse univariate, sparse multivariate for which different data structures and algorithms have been implemented. When it pays off, Karatsuba multiplication, division by multiplication with the modular inverse or exponentiation by generating functions are used. Conversions between different types of polynomials have also been implemented.

An interface allows calling the library’s functions from within Mathematica and provides the user with faster commands for expanding polynomial expressions, dividing polynomials and computing modular inverses of polynomials.

A NEW EFFICIENT ALGORITHM FOR COMPUTING GRÖBNER BASES WITHOUT REDUCTION TO ZERO (F_{5})

Jean-Charles Faugere Project SPACES LIP6/CNRS/Univ P6 case 168, 4 pl. Jussies F-75252 Paris Cedex 05 - FRANCE Jean-Charles.Faugere@lip6.fr

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 F5 shows that it is also very efficient in practice: for instance previously untractable problems can be solved (cyclic 10). We illustrate this algorithm by one detailed example.

COMPUTING POLYNOMIAL JANET BASES

Vladimir P. Gerdt Laboratory of Information Technologies Joint Institute for Nuclear Research 141980 Dubna, Russia gerdt@jinr.ru

In this talk we consider algorithmic and computational aspects in construction of polynomial Janet bases which are typical representatives of involutive bases and usually redundant as Gröbner ones. We present an advanced involutive algorithm for computing minimal Janet bases and appropriate data structures. One of the attractive features of the algorithm is its efficient parallelization that preserves a strategy for selection of nonmultiplicative prolongations to be examined. The effect of parallelism will be demonstrated for modular computation on an two-processor computer. For the conventional sequential computation we compare efficiency of our C-code implementing the involutive algorithm with those in computer algebra systems Singular and Magma providing fast implementation of the Buchberger algorithm for computing reduced Gröbner bases. As benchmarks we use the collection of polynomial systems widely exploited for testing Gröbner base+-s software. Applicability of Janet bases to computing toric ideals will be also discussed.

COMPUTING THE TOPOLOGY OF REAL ALGEBRAIC SURFACES

Patrizia Gianni Dipartimento di Matematica Università di Pisa - ITALY gianni@dm.unipi.it

Constructive algorithms to determine the topological type of a non-singular real algebraic projective surface S in the real projective space are presented. Starting from a polynomial equation with rational coefficients for S we compute the homology of the various connected components of the surface. The homology is reconstructed in a finite number of steps, using as a basic tool Morse theory.

ALGEBRAIC AND NUMERICAL TECHNIQUES FOR COMPUTING OFFSETS

Laureano Gonzalez-Vega Departamento de Matematicas, Estadistica y Computacion Universidad de Cantabria - SPAIN gvega@matesco.unican.es

Geometric modeling by using implicit algebraic surfaces is becoming a very active research area in Computer Aided Geometric Design: in fact the simultaneous availability of the parametric and the implicit representation of a surface is extremely useful when solving central problems such as offsetting. We formulate this problem as a parametrized first order system of ordinary differential equations whose solution curve will be determined either numerically or in terms of power series whose parameter will be its arc length. Before solving the involved paarametric system of differential equations, an algebraic/topological analysis of the considered surfaces is performed in order to determine the number connected components and to detect singularities, autointersections, etc. As a by-product, these algorithms motivate the introduction of the notion of ”topological offset” where the attention is more focused in shape than in distance: for most distances the offset of a parabola is not topologically a parabola (including the appearing of a singular point). Algorithms computing and manipulating these topological offsets will be also presented.

APPLICATIONS OF COMMUTATIVE ALGEBRA TO CODING THEORY

Martin Kreuzer NWF 1 -Mathematik Universitat Regensburg D - 93040 Regensburg, GERMANY martin.kreuzer@mathematik.uni-regensburg.de

In this talk we describe some relations between certain 1-dimensional graded rings and linear codes associated to them. We compute the basic invariants (length, dimension, minimal distance) of those codes in terms of ring theoretic and geometric invariants. Moreover, we give an explicit description of the dual codes using the canonical ideal of the ring. Classical problems from Coding Theory are translated into the language of Commutative Algebra and used to motivate further studies in the field of 1-dimensional graded rings.

CENTRAL CONFIGURATIONS OF FOUR GRAVITATIONAL MASSES WITH AN AXYS OF SYMMETRY

Daniel Lazard LIP6 (Laboratoire d’Informatique de Paris VI) 8 rue du Capitaine Scott F-75015 Paris - France Daniel.lazard@lip6.fr

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. In the case where none of the masses are on the axis (trapeze configuration), it is rather easy to show that for any value of the two masses, there is exactly one central configuration.

In the case of two masses on the axis and two symmetric masses normalized to 1 (this is the only other case if the bodies are not aligned), some reductions allow to model the problem by the system of equations

(b − d)^{2} − 2(b + d) + 1 + f0,
m(B − 1) − (D − F)(d − b + 1)0,
n(D − 1) − (B − F)(b − d + 1)0,
b^{3}B^{2}1,  d^{3}D^{2}1,  f^{3}F^{2}1.

where m and n are the remaining masses, the lower case other variables are squares of distances and the upper case variables are the cubes of the inverses of the same distances. Thus all variables should be positive. This system seems rather simple; however it is not having a Bezout number of 1000 and 102 complex solutions for m and n fixed.

The number of central configurations is 1, 3 or 5 depending on the values of the masses m and n. This number is determined by the position of the point (m, n) relatively to a plane curve in the space of the masses. The implicit equation of this curve has degree 424, more than 50,000 monomials and integer coefficients of more 200 decimal digits.

For proving this result, we have designed a general algorithm for discussing zero-dimensional problems depending on few parameters. In this particular case, it needs algorithms for Gröbner basis computation, for elimination, for drawing plane curves, for the certification of a drawing (proving that no branch is omitted) and for fast real solving zero-dimensional systems of equations.

The size of the curve which is a part of the solution shows that this problem is near from the limit of the present technology, and we guess that the only software which is presently able to do such a computation is the last version of FGb/RealSolving, which is developed in our team.

FILTER DESIGN USING GRÖBNER BASES

Jerome Lebrun I3S - CNRS - Sophia-Antipolis, France lebrun@i3s.unice.fr

Wavelets and filter banks have become useful in digital signal processing in part because of their ability to represent piecewise smooth signals with relative efficiency. For such signals, the discrete wavelet transform (DWT) developed as a main tool for signal compression (JPEG 2000), fast algorithms, and signal estimation and modeling (noise suppression and image segmentation, etc). The DWT is usually implemented as an iterated digital filter bank tree, so the design of a wavelet transform amounts to the design of a filter bank.

While the spectral factorization approach is the most convenient method to construct the classic Daubechies wavelets (and the corresponding digital filters), it is not applicable anymore to most of the other wavelet design problems where additional constraints are imposed. A typical case comes with the construction of multiwavelets (corresponding to filter banks with relaxed requirements on their time-invariance). Multiwavelets are a natural generalization of wavelets where one allows the associated multiresolution analysis to be generated by more than one scaling function so as to overcome the limitation preventing the construction of orthogonal wavelets with compact support and symmetries. Conditions of balancing are then introduced in the design so as to ensure that the multiwavelets behave like bona-fide wavelets up to a given order of approximation. These conditions and stronger conditions of interpolation leading to multiCoiflets will be extensively detailed.

Besides, although the spectral factorization approach can not be used anymore, as for many of these design problems, the design equations can be written as a multivariate polynomial system of equations. Accordingly, Groebner bases algorithms offer a way to obtain solutions in these cases. At the same time, even though the computation of a Groebner basis is the crucial point in our approach, one should not forget that it is only the first step in the solving process. Methods to implement change of ordering of the Groebner basis, and alternative techniques leading to triangular systems and rational univariate representation of the system are also key tools. Some of these methods will be discussed.

NEIGHBORHOODS OF EMPIRICAL POLYNOMIALS

Valentina Marotta Dipartimento di Matematica e Informatica Viale A. Doria, 6 95125 Catania - ITALY marotta@dmi.unict.it

Whenever the coefficients of a polynomial have limited accuracy, it is called an empirical polynomial. This led to a new branch of classic polynomial algebra, the numerical polynomial algebra, whose aim is to accommodate the presence of inaccurate data and inexact computation combining methods in computer algebra and numerical analysis. Since a polynomial is not exact, we consider a family of polynomials called neighborhood. In this context we give a new approach based on the idea of using resultant in order to know the common factors between an empirical polynomial and a generic polynomial in its neighborhood. Moreover given a polynomial, the Square Free property for the polynomials in its neighborhood is investigated. Finally the problem of computing an approximate GCD between two empirical polynomials is the object of our interest.

SYMBOLIC-NUMERIC SOLVERS FOR GEOMETRIC APPLICATIONS

Bernard Mourrain INRIA, 2004 Route des Lucioles BP 93, 06902 Sophia-Antipolis - FRANCE mourrain@sophia.inria.fr

The interaction between algebra and geometry is a long story. It involves the manipulation of algebraic numbers or the resolution of polynomial equations, which is particularly crucial nowadays in many applications, going from CAD to Computer vision. In this talk, we will give a brief overview of different approaches for tackling this question, including analytic, homotopic, subdvision, algebraic and geometric methods. These will be illustrated in problems on (algebraic) curves and surfaces.

TORIC IDEALS AND STATISTICAL MODELS

Fabio Rapallo DIMA - Dipartimento di Matematica Via Dodecaneso, 35 16146 Genova - ITALY rapallo@dima.unige.it

In this talk we present the links between the algebraic theory of toric = ideals and the analysis of probability models for discrete data. Some = new techniques of statistical inference based on algebraic results are = mentioned. The talk is divided in two parts. In the first part, we describe the basic statistical framework of the = analysis of discrete data, defining as simply as possible the = fundamental topics such as the definition of a statistical model, the = likelihood and the notion of sufficient statistic. In particular, we = review the basic properties of the discrete probability spaces, the = definition of the likelihood function and the method of maximum = likelihood for parameter estimation. Moreover, the notions of log-linear = model and conditional inference are presented. Using some examples of = discrete data – and in particular some simple contingency tables – we = describe a new statistical technique of goodness-of-fit testing for = log-linear models based on the key notion of Markov basis. In = particular, we show how the conditional inference uses the algebraic = results of the theory of toric ideals. The algebraic methods are based = on a computational tool, namely the computatation of Gröbner bases of = toric ideals in order to compute Markov bases.

In the second part, we give a complete review on the recent literature about this topic, starting from the pioneering work of Diaconis and Sturmfels. We point out the main statistical problem derived from the Diaconis–Sturmfels paper and the most recent research interests. As the Markov basis depends on the sample space and on the functional form of the sufficient statistics, the main problems are the computation or the characterization of Markov bases for large classes of log-linear models and the determination of the degree of the polynomials in the relevant Gröbner basis.

SINGULAR ON A WEB-SERVER

Marko Roczen Institut für Mathematik Rudower Chaussee 25 Humboldt-Universität, D-10099 Berlin - GERMANY roczen@mathematik.hu-berlin.de

When called via a www-server, Singular can generate ”books on demand” which meet the reader’s interest more than a classical textbook. This is presented and explained for a course on linear algebra, where texts and exercises with randomly chosen parameters are organized in their logical context. Requests via HTML-forms make things platform-independent.

GRÖBNER BASES RELATED TO 3-DIMENSIONAL TRANSPORTATION PROBLEMS

Fabio Rossi^{1} Dipartimento di Scienze Matematiche Università degli Studi di Trieste Via A. Valerio 12/1 34127 - Trieste - Italy rossif@univ.trieste.it

The aim of this talk is to illustrate some work in progress on 3-dimensional transportation problems. A typical problem of this kind goes as follows. Given r production facilities F_{1} … F_{r}, let a_{ik} (i : 1 … r, k : 1 … t) denote the number of units of an indivisible good produced by F_{i} during the k-th month of a fixed period of t months. Assume that there are s outlets O_{1} … O_{s} each one demanding a certain number of units per month, say b_{jk} (j : 1 … s, k : 1 … t). If c_{ijk} stands for the cost associated with transporting one unit from F_{i} to O_{j} during the k-th month, one wishes to minimize the total cost of transportation during the whole period of t months.

1Co-author: Giandomenico Boffi, Dipartimento di Scienze, Università Gabriele d’Annunzio, Viale Pindaro 42, 65127 - Pescara - Italy, gboffi@unich.it

In mathematical terms, one wishes to solve the integer programming problem associated with the matrix A whose columns are

\{\underline{e}_{ij} ⊕ \underline{e}ik^{′} ⊕ \underline{e}jk^{′′} | 1 ≤ i ≤ r, 1 ≤ j ≤ s, 1 ≤ k ≤ t\},

where \{\underline{e}_{ij}\} (resp., \{\underline{e}ik^{′}\} ; resp., \{\underline{e}jk^{′′}\} ) stands for the canonical basis of the ℤ-module of r × s (resp., r × t ; resp., s × t) integer matrices.

It is well known that integer programming problems as above can be solved by a method first suggested by Conti and Traverso, which resorts to the calculation of suitable Gröbner bases.

More precisely, if I_{A} denotes the toric ideal canonically associated with the matrix A described before, then one needs to find the reduced Gröbner basis of I_{A} relative to some appropriate term order.

In this talk we show how to find the reduced lexicographic Gröbner basis of I_{A} using graph theory.

As for the specific results we obtain, we give a complete description in case rst3, which in turn outlines a strategy for every case such that 3 ∈ {r, s, t}. We tend to believe that no essential change takes place when 3 ∉ {r, s, t}, but the combinatorics looks much less manageable.

The main result is the following:

Theorem Let rst3 and set the following:

S_{1} : \{all degree 4 triplets of cycles of G_{\underline{3}×\underline{3}×\underline{3}}\},
S_{2} : \{all degree 6 triplets of cycles of G_{\underline{3}×\underline{3}×\underline{3}}\},
S_{3} : \{all non-divisible degree 7 triplets of cycles of G_{\underline{3}×\underline{3}×=\underline{3}}\},
S : S_{1} ∪ S_{2}∪ = S_{3},
Gr : {all binomial associated with the elements of S}.

Then Gr is the reduced Gröbner basis of I_{A} with respect to <_{Lex}.

USING THE SYNDROME VARIETY TO STUDY CYCLIC CODES

Massimiliano Sala Department of Mathematics University of Pisa, Italy sala@dm.unipi.it

Cyclic codes are the class of Error Correcting Codes, which is most widely used, containing in particular BCH codes and Reed-Solomon codes.

There are three important methods based on Gröbner bases techniques which allow the decoding of generic cyclic codes: the CRHT algorithm, its improvement by Caboara and Mora and the algorithm by Loustaunau and York. All of them are based on the beautiful description of the algebraic variety containing occurred errors by Chen, Reed, Helleseth and Truong ([ChReHeTr94]). Let S_{C}{h_{1}, …, h_{v}} be the defining set of an 𝔽_{q} [n, k, d] cyclic code C. Consider the variables {x_{j}, z_{i}, y_{i} | 1 ≤ j ≤ n − k, 1 ≤ i ≤ t} and the following system: {y_{1}z_{1}^{i_{j}} +y_{2}z_{2}^{i_{j}} +⋯+y_{t}z_{t}^{i_{j}} −x_{j}0, z_{i}^{n+1} −z_{i}0, y_{i}^{q−1} −10} Then the z_{i} correspond to the locations of the errors, the y_{i} to their values and the x_{j} to the syndromes.

The CRHT syndrome variety has been used by the author to find the distance of cyclic codes.

We are studying further improvements of the methods based on the CRHT variety, both of the decoding procedure and of the method to get the distance. Moreover, the author is exploiting the CRHT variety to get some description of minimum weight words.

\underline{References} [ChReHeTr94] X. Chen, I.S. Reed, T. Helleseth, K. Truong, “Use of Gröbner Bases to Decode Binary Cyclic Codes up to the True Minimum Distance”, IEEE Trans. on Inf. Th., vol. 40, p. 1654–1661, 1994.

DATA REPRESENTATIONS IN THE COMPUTER ALGEBRA SYSTEM SINGULAR

Hans Schönemann University of Kaiserslautern Department of Mathematics PB 3049 Kaiserslautern, 67653 - GERMANY hannes@mathematik.uni-kl.de

The method of Gröbner bases (GB) is undoubtly one of the most important and prominent success stories of the field of computer algebra. Unfortunately, these algorithms have a worst case exponential time and space complexity and tend to tremendously long running times and consumption of huge amounts of memory. While algorithmic improvements led to more successful algorithms for many classes of problems, an efficient implementation is necessary for all classes of problems: Analyzing GB computations from an implementation point of view leads to many interesting questions. For example: How should polynomials and monomial be represented and their operations be implemented? What is the best way to implement coefficients? How should the memory management be realized?

Singular 2-0 uses generalized exponent vectors, which may contain degree fields and contains the exponents as bit fields in an order given by the monomial ordering. The monomial operations on generalized exponent vectors can be used to add and subtract them efficiently using vectorized implementations Even divisibility test can be vectorized, but we use a pre-test. This approach can be applied to any monomial ordering.

Other improvements in the new Singular 2-0 will be also discussed: geo bucket approach for polynomial reductions (and other operations) and a customized memory management.

Some of these techniques are well known - we try to give an overview of the history of GB implementations.

MANAGING INSTABILITY IN FLOATING POINT GRÖBNER BASIS COMPUTATION

Carlo Traverso Dipartimento di Matematica Via Buonarroti 2, 56127 Pisa - ITALY traverso@dm.unipi.it

Let F {f_{1}, …, f_{n}} be a set of polynomials in a (multivariate) polynomial ring k[X] endowed with a term-ordering; we say that F is unstable if the Gröbner basis of the ideal generated by F differs “substantially” from the Gröbner basis of the ideal generated by “nearby” polynomial sets F′.

Of course, to transform this into a definition, we need to specify what is a “substantial difference” and what is the space in which we look for neighboring polynomial sets. Obvious choices for the space of polynomial sets is the space of n-tuples of polynomials with given degrees (dense polynomials), or the space of polynomial sets with given power products (sparse polynomials), but other choices might be restricted to polynomial sets such that the generated ideal is non trivial, or which has a suitable dimension, multiplicity or Hilbert polynomial. The “substantial difference” might be defined in terms of continuity, of the staircase, of the Hilbert function etc.

Unstable polynomial sets usually do not give problems for the computation of a Gröbner basis, when their coefficients are exactly known, and exact arithmetic is used; special arithmetic techniques allow to compute a Gröbner basis using inexact arithmetic when an exact input is known, [1,11]; when however the input is inexact, the situation is much more complicated: an exact handling of inexact, unstable data is (by definition) catastrophic; in this paper we want to discuss how to handle this situation with suitable floating point arithmetic and special Gröbner techniques. The work is partly to be done, since it relies heavily on experimental work, requiring the implementation of suitable software, and the experimental material is scarce.

\underline{References}

[1] C. Bonini, K.-P. Nischke, C. Traverso Computing Gröbner bases numerically: some experiments proceedings SIMAI (1998)

[2] M. Caboara, C. Traverso, Efficient algorithms for ideal operations , ISSAC 98, 225 (1998)

[3] J.-C. Faugère A new efficient algorithm for computing Gröbner bases (F_{4}) MEGA-98, JPAA (1999)

[4] FRISCO test suite http://www.inria.fr/saga/POL/

[5] A. G. Khovanski, Fewnomials, Amer. Math. Soc., Providence, RI, (1991).

[6] The GNU multiprecision package, ftp://prep.ai.mit.edu

[7] PoSSoLib-3.0.1, ftp://posso.dm.unipi.it

[8] H.J. Stetter Stabilization of polynomial system solving with Gröebner bases proceedings ISSAC (1997)

[9] K. Shirayanagi. Floating Point Gröbner Bases Journal of Mathematics and Computers in Simulation 42, pp. = 509-528 (1996)

[10] C. Traverso. Hilbert functions and the Buchberger algorithm J. Symbolic Comput. 22, no. 4, 355–376. (1996)

[11] A. Zanoni, Numerical stability in Gröbner basis computation, submitted to RWCA 2001

GRÖBNER BASES AND CODING THEORY

Barry Trager IBM T.J.Watson Research Center P.O. Box 218Yorktown Heights, NY 10598 - USA bmt@watson.ibm.com

The decoding process for alternant codes (which include Reed-Solomon, BCH and Goppa codes as special cases) can be reduced to the resolution of an equation, called the key equation, which is of the form p ≡ qs mod x^{2t}, where p, q, s ∈ F [x]. The set of solution pairs (p, q) form a rank 2 free module over F [x]. We investigate a family of algorithms which involve incrementally modifying solutions to this equation to produce other solutions having desired properties. All of these algorithms can be derived using a common technique of finding the submodule of solutions which satisfies particular linear constraints. This approach leads to both efficient algorithms and very simple proofs of correctness.

SOME COMPUTATIONAL METHODS IN D-MODULES. OPEN PROBLEMS.

Jose Maria Ucha Departamento de Algebra Universidad de Sevilla - SPAIN ucha@algebra.us.es

Calculation of the Bernstein-Sato ideals, comparation of logarithmic D-modules and calculation of the slopes are three examples of how the computational methods are starting to be considered as a fundamental tool in the context of D-modules theory. In this talk we describe these techniques and present some related open problems.

QUADRATIC FORMS AND THE PARAMETRIZATION PROBLEM

Franz Winkler RISC-Linz, J. Kepler University Linz, A-4040 Austria Franz.Winkler@risc.uni-linz.ac.at

Algebraic curves and surfaces play an important and ever increasing role in computer aided geometric design, computer vision, and computer aided manufacturing. Consequently, theoretical results need to be adapted to practical needs. We need efficient algorithms for generating, representing, manipulating, analyzing, rendering algebraic curves and surfaces. In the last years there has been dramatic progress in all areas of algebraic computation. In particular, the application of computer algebra to the design and analysis of algebraic curves and surfaces has been extremely successful.

One interesting subproblem in algebraic geometric computation is the rational parametrization of curves and surfaces. The tacnode curve defined by f(x, y)2x^{4} − 3x^{2}y + y^{4} − 2y^{3} + y^{2} in the real plane has the rational parametrization

x(t)\frac{t^{3} − 6t^{2} + 9t − 2}{2t^{4} − 16t^{3} + 40t^{2} − 32t + 9}, y(t)\frac{t^{2} − 4t + 4}{2t^{4} − 16t^{3} + 40t^{2} − 32t + 9}

over ℚ. The criterion for parametrizability is the genus. Only curves of genus 0 have a rational parametrization, and only surfaces of arithmetic genus 0 and second plurigenus 0 have a rational parametrization.

Computing parametrizations essentially requires the full analysis of singularities (either by successive blow-ups, or by Puiseux expansion) and the determination of regular points on the curve or surface. We can control the quality of the resulting parametrization by controlling the field over which we choose these regular points. Thus, finding a regular curve point over a minimal field extension on a curve of genus 0 is one of the central problems in rational parametrization of curves, compare [SeWi97] and [HiWi98]. Similarly, finding rational curves on surfaces leads to parametrizations, compare [LSWH00] and [LSW01]. We discuss methods for finding such rational points of curves and rational curves on surfaces.

\underline{References}

[HiWi98] E. Hillgarter, F. Winkler, “Points on Algebraic Curves and the Parametrization Problem”, in Automated Deduction in Geometry, D. Wang (ed.), Springer-Verlag, 189–207 (1998).

[SeWi97] J.R. Sendra, F. Winkler, “Parametrization of Algebraic Curves over Optimal Field Extensions”, J. Symbolic Computation 23/2&3, 191–207 (1997).

[LSWH00] G. Landsmann, J. Schicho, F. Winkler, E. Hillgarter, “Symbolic Parametrization of Pipe and Canal Surfaces”, Proc. ISSAC’00, 202–208, C. Traverso (ed.), ACM Press (2000).

[LSW01] G. Landsmann, J. Schicho, F. Winkler, “The Parametrization of Canal Surfaces and the Decomposition of Polynomials into a Sum of Two Squares”, J. Symbolic Computation 32/1&2, 119–132 (2001).

EXPERIMENTS ON NUMERICAL GRÖBNER BASES

Alberto Zanoni Dipartimento di Matematica ”Ulisse Dini” V.le G. B. Morgagni 67/A 50134 Firenze - ITALY alberto.zanoni@tiscalinet.it

Floating point numerical Groebner bases computation may be used to limit computation space and time due to excessive coefficient growth and / or manage inexact initial data, but without any particular treatment, the obtained result is very often the trivial ideal, or may have different properties with respect to its integer / exact version (different staircase, number/multiplicity of solutions, etc.) Error spreading (meaningful bits loss) in numerical Groebner bases computation is tested and analysed by means of two new types of coefficients (hybrids - having a mod p component and a floting point one - and double floats), to measure the stability of a system under small deformations. Some cases are considered (DegRevLex and Lex orderings), and for them an ”asymptotic” experimental precision loss is obtained. To see more deeply what’s going on, a symbolic analysis is also proposed, which uses an extra variable to compute intrinsic stability parameters, according to different criteria. Some other possible Buchberger’s algorithm tuning modalities and types of analysis are also sketched.