| 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 |
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 |
Many data are often üncertain" 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].
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 |
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 (F5) |
| 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 |
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 |
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 |
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 |
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 |
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 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 |
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 |
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 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 |
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 F1¼Fr, let aik (i: 1 ¼r, k: 1 ¼t) denote the number of units of an indivisible good produced by Fi during the k-th month of a fixed period of t months. Assume that there are s outlets O1¼Os each one demanding a certain number of units per month, say bjk (j: 1 ¼s, k: 1 ¼t). If cijk stands for the cost associated with transporting one unit from Fi to Oj during the k-th 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 IA denotes the toric ideal canonically associated with the matrix A described before, then one needs to find the reduced Gröbner basis of IA relative to some appropriate term order.
In this talk we show how to find the reduced lexicographic Gröbner basis of IA 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
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 SC {h1,¼,hv} be the defining set of an \mathbb Fq [n,k,d] cyclic code C. Consider the variables {xj,zi,yi | 1 £ j £ n-k, 1 £ i £ t} and the following system: { y1 z1ij + y2 z2ij + ... + yt ztij - xj 0, zin+1-zi 0, yiq-1-1 0 } Then the zi correspond to the locations of the errors, the yi to their values and the xj 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. 1654-1661, 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 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 |
Let F {f1,...,fn} 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.
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 (F4) 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 |
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 x2t,
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) 2x4-3x2y+y4-2y3+y2 in the real plane has the 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.
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 Ülisse 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 äsymptotic"
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.
di Scienze,
Università Gabriele d'Annunzio,
Viale Pindaro 42, 65127 - Pescara - Italy, gboffi@unich.it