Workshop on 
Applications of Commutative Algebra 
April 36, 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 
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 
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 
[9] Marotta V.: Resultants and Neighborhoods of a Polynomial., preprint 2000
[12] S. Wolfram: The Mathematica Book, 4th ed., Wolfram Media, = Cambridge University Press, 1999
A LIBRARY FOR POLYNOMIAL ARITHMETIC 
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}) 
JeanCharles Faugere 
Project SPACES LIP6/CNRS/Univ P6 
case 168, 4 pl. Jussies 
F75252 Paris Cedex 05  FRANCE 
JeanCharles.Faugere@lip6.fr 
COMPUTING POLYNOMIAL JANET BASES 
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
twoprocessor computer. For the conventional sequential
computation we compare efficiency of our Ccode 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 
Constructive algorithms to determine the topological type of a
nonsingular 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 
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 byproduct, 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 
In this talk we describe some relations between certain
1dimensional 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 1dimensional graded rings.
CENTRAL CONFIGURATIONS OF FOUR GRAVITATIONAL MASSES 
WITH AN AXYS OF SYMMETRY 
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

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 zerodimensional 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 zerodimensional 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 
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 timeinvariance). 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 bonafide 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 
SYMBOLICNUMERIC SOLVERS FOR GEOMETRIC APPLICATIONS 
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 
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 loglinear =
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 goodnessoffit testing for =
loglinear 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 DiaconisSturmfels 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 loglinear models and the
determination of the degree of the polynomials in the relevant
Gröbner basis.
SINGULAR ON A WEBSERVER 
Marko Roczen 
Institut für Mathematik 
Rudower Chaussee 25 
HumboldtUniversität, D10099 Berlin  GERMANY 
roczen@mathematik.huberlin.de 
GRÖBNER BASES RELATED TO 3DIMENSIONAL 
TRANSPORTATION PROBLEMS 
The aim of this talk is to illustrate some work in progress on 3dimensional 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 kth 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 kth month, one wishes to minimize the total cost of transportation during the whole period of t months.
In mathematical terms, one wishes to solve the integer programming
problem associated with the matrix A whose columns are

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 r s t 3, 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 r s t 3 and set the following:

USING THE SYNDROME VARIETY TO STUDY CYCLIC CODES 
Cyclic codes are the class of Error Correcting Codes, which is
most widely used, containing in particular BCH codes and
ReedSolomon 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 \mathbb F_{q} [n,k,d] cyclic code C. Consider the variables {x_{j},z_{i},y_{i}  1 £ j £ nk, 1 £ i £ t} and the following system: { y_{1} z_{1}^{ij} + y_{2} z_{2}^{ij} + ... + y_{t} z_{t}^{ij}  x_{j} 0, z_{i}^{n+1}z_{i} 0, y_{i}^{q1}1 0 } 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.
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. 16541661, 1994.
DATA REPRESENTATIONS IN THE COMPUTER 
ALGEBRA SYSTEM SINGULAR 
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 20 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 pretest. This approach can be applied to any monomial ordering.
Other improvements in the new Singular 20 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 
Let F {f_{1},...,f_{n}} be a set of polynomials in a
(multivariate) polynomial ring k[X] endowed with a
termordering; 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 ntuples 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.
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}) MEGA98, 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] PoSSoLib3.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. = 509528 (1996)
[10] C. Traverso. Hilbert functions and the Buchberger algorithm J. Symbolic Comput. 22, no. 4, 355376. (1996)
[11] A. Zanoni, Numerical stability in Gröbner basis computation, submitted to RWCA 2001
GRÖBNER BASES AND CODING THEORY 
The decoding process for alternant codes (which include
ReedSolomon, 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 DMODULES. OPEN PROBLEMS. 
Jose Maria Ucha 
Departamento de Algebra 
Universidad de Sevilla  SPAIN 
ucha@algebra.us.es 
QUADRATIC FORMS AND THE PARAMETRIZATION PROBLEM 
Franz Winkler 
RISCLinz, J. Kepler University Linz, A4040 Austria 
Franz.Winkler@risc.unilinz.ac.at 

EXPERIMENTS ON NUMERICAL GRÖBNER BASES 
Alberto Zanoni 
Dipartimento di Matematica Ülisse Dini" 
V.le G. B. Morgagni 67/A 
50134 Firenze  ITALY 
alberto.zanoni@tiscalinet.it 
di Scienze,
Università Gabriele d'Annunzio,
Viale Pindaro 42, 65127  Pescara  Italy, gboffi@unich.it