|
C
O
C
O
A
Research Team in Genova | ||
| commutative and computer algebra | ||
| COCOA's Home | cocoa at dima.unige.it | Last Modified: 21 May 2008 |
| Abstracts |
|
John Abbott, Claudia Fassino, Maria Laura Torrente Stable Border Bases for Ideals of Points BibTeX, dvi |
|
John Abbott, Claudia Fassino, Maria Laura Torrente Thinning Out Redundant Empirical Data BibTeX, dvi |
|
Lorenzo Robbiano Algebra Lineare per tutti BibTeX |
|
John Abbott Challenges in Computational Commutative Algebra In this paper we consider a number of challenges from the point of view of the CoCoA pro ject one of whose tasks is to develop software specialized for computations in commutative algebra. Some of the challenges extend considerably beyond the boundary of commutative algebra, and are addressed to the computer algebra community as a whole. BibTeX |
|
John Abbott The Design of CoCoALib This document describes some of the more important design features of Co- CoALib, a C++ library for computations in commutative algebra with partic- ular focus on Gröbner bases. For almost 20 years the CoCoA pro ject has been conducting research into computational commutative algebra, developing new algorithms and offering implementations in the interactive program "CoCoA". Recently we took the decision to rebuild the software from scratch with the specific aim of making excellent implementations available to all researchers. The implementations will be accessible in three distinct ways: - as a standalone interactive system - as a networked service (via an OpenMath-like communications channel) - as a C++ library, called CoCoALib CoCoALib, being the core, is the most evolved part of the pro ject, and is the part we shall look at most closely. The software is to be free in the sense of the GPL. BibTeX |
|
Lorenzo Robbiano Three friends and computer algebra BibTeX |
|
Anna M. Bigatti, Anthony V. Geramita Level Algebras, Lex Segments and Minimal Hilbert Functions In this paper we prove the existence of minimal level artinian graded algebras having socle degree r and type t and describe their h-vector in terms of the r-binomial expansion of t. We also investigate the graded Betti numbers of such algebras and completely describe their extremal resolutions.
We also show that any set of points in Pn whose Hilbert function
has first difference
as described above, must satisfy the Cayley-Bacharach property. |
|
Anna M. Bigatti, Aldo Conca, Lorenzo Robbiano Generic Initial Ideals and Distractions The generic initial ideals of a given ideal are rather recent invariants. Not much is known about these objects, and it turns out to be very difficult to compute them. The main purpose of this paper is to study the behaviour of generic initial ideals with respect to the operation of taking distractions. Theorem~\ref{gindl=I} is our main result. It states that the {\tt DegRevLex}-generic initial ideal of the distraction of a strongly stable ideal is the ideal itself. In proving this fact we develop some new results related to distractions, stable and strongly stable ideals. We draw some geometric conclusions for ideals of points. BibTeX, dvi |
|
Massimo Caboara, Martin Kreuzer, Lorenzo Robbiano Minimal Sets of Critical Pairs In the computation of a Gröbner basis using Buchberger's algorithm, a key issue for improving the efficiency is to produce good techniques for avoiding as many unnecessary critical pairs as possible. A good solution would be to avoid all non-minimal critical pairs, and hence to process only a minimal set of generators of the module generated by the critical pairs. In this paper we show how to obtain that desired solution while retaining the same efficiency as with the classical implementation. As a consequence, we get a new Optimized Buchberger Algorithm. BibTeX, dvi |
|
Laura Bazzotti, Giorgio Dalzotto, Lorenzo Robbiano Remarks on Geometric Theorem Proving The dream of deducing all the theorems of a specific sector of mathematics from a small set of axioms, has fascinated many mathematicians not least of which David Hilbert. The dream did not come true due to the fundamental work of Kurt Goedel, from which it became clear that it is not possible to construct a machine which proves all possible theorems. However, the door was left open to the possibility of using a machine to prove some theorems. The purpose of this paper is to contribute to the subject in many ways. First of all, we want to look at the fundamentals of the theory on a purely algebraic basis, where ideal theory provides the necessary devices. Along the way, we introduce important notions such as the computing field, the optimal hypothesis ideal, and the good set of conditions.
We also provide an implementation of our method in the system
CoCoA, which uses Groebner bases. But, since we mainly concentrate
on the representation of knowledge, the tools for proving
(Groebner bases, Wu-Ritt bases or other devices) are considered to be
of lesser importance. |
|
Anna M. Bigatti, Lorenzo Robbiano Toric Ideals Toric ideals are binomial ideals which represent the algebraic relations of finite sets of power-products. Their importance comes from on the fact that they show up in many problems arising from different branches of science, for instance Integer Programming and Combinatorics. Largely inspired by the fundamental book by Sturmfels, we have recently addressed the problem of computing toric ideals and even more recently we became aware of a new use of toric ideals in Statistics.
The broadening scope of use of this beautiful piece of theory
suggested the need for the present paper, which is mainly expository,
although it contains some important remarks which we were unable to
find in the literature.
|
|
Massimo Caboara, Lorenzo Robbiano Families of Estimable Terms In this paper we present a full solution to an open problem in Design of Experiments, a branch of Statistics, which can equally be seen as a problem in Algebraic Geometry. Given a complete set O of estimable terms, we are able to find all the fractions F of a full factorial design, such that the images of O form a basis of P/I(F) as a K-vector space. This fact can be rephrased as a result in the theory of zero-dimensional schemes. BibTeX, dvi |
|
Lorenzo Robbiano Zero-Dimensional Ideals, or, The inestimable Value of Estimable Terms This survey describes several aspects of the theory of zero-dimensional ideals. It is organised according to the following themes:
BibTeX, dvi |
|
John Abbott Sparse Squares We answer a question left open in an article of Coppersmith and Davenport which proved the existence of polynomials whose powers are sparse, and in particular polynomials whose squares are sparse (i.e. the square has fewer terms than the original polynomial). They exhibit some polynomials of degree 12 having sparse squares, and ask whether there are any lower degree complete polynomials with this property. We answer their question negatively by reporting that no polynomial of degree less than 12 has a sparse square, and explain how the substantial computation was effected using the system CoCoA. BibTeX, dvi |
|
John Abbott, Anna M. Bigatti, Martin Kreuzer, Lorenzo Robbiano Computing Ideals of Points We address the problem of computing ideals of polynomials which vanish at a finite set of points. In particular we develop a modular Buchberger-Möller algorithm, best suited for the computation over the rational numbers, and study its complexity; then we describe a variant for the computation of ideals of projective points, which uses a direct approach and a new stopping criterion. The algorithms are implemented in CoCoA3.6, and we report some experimental timing. BibTeX, dvi |
|
John Abbott, Anna M. Bigatti, Martin Kreuzer, Lorenzo Robbiano Computing Ideals of Points We address the problem of computing ideals of polynomials which vanish at a finite set of points. In particular we develop a modular Buchberger-Möller algorithm, best suited for the computation over the rational numbers, and study its complexity; then we describe a variant for the computation of ideals of projective points, which uses a direct approach and a new stopping criterion. The algorithms are implemented in CoCoA3.6, and we report some experimental timing. BibTeX, dvi |
|
John Abbott, Victor Shoup, Paul Zimmermann Factorization in Z[x]: the searching phase In this paper we describe ideas used to accelerate the Searching Phase of the Berlekamp-Zassenhaus algorithm, the algorithm most widely used for computing factorizations in Z[x]. Our ideas do not alter the theoretical worst-case complexity, but they do have a significant effect in practice: especially in those cases where the cost of the Searching Phase completely dominates the rest of the algorithm. A complete implementation of the ideas in this paper is publicly available in the library NTL. We give timings of this implementation on some difficult factorization problems. BibTeX, dvi |
|
Anna M. Bigatti, Roberto La Scala, Lorenzo Robbiano Computing Toric Ideals Toric ideals are binomial ideals which represent the algebraic relations of sets of power-products. They show up in many problems arising from different branches of Mathematics. In this paper we develop new pieces of theory which allow to device a parallel algorithm and an efficient elimination algorithm. In many respects they improve existing algorithms for the computation of toric ideals. BibTeX |
|
Massimo Caboara, Marco Silvestri A Classification of compatible module ordering The term-orderings on a polynomial ring are strictly related with the computation of Gröbner bases and the efficiency of Buchberger Algorithm; they are classified by Robbiano. Gröbner bases and Buchberger Algorithm have been generalized to modules of a polynomial ring with similar applications toward commutative algebra. As a consequence of that, module term-orderings have been investigated but not completely classified. The aim of this note is to give a complete classification for the module term-orderings which are compatible with their ring term-orderings. The orderings encountered in practice invariably belong to this class. Given a free module M:=R^r over the polynomial ring R = k[\xx] it is possible to embed M in a overring S:=k[\xx,\yy] in such a way that M is a subring of S. As a consequence each term-ordering in S which extends one of M induces a term-ordering on M. We prove in this paper the converse, so deriving the classification. BibTeX |
|
John Abbott Univariate Factorization over the Integers In this article we address a number of aspects relevant to the practical factorization of univariate polynomials over Z. In particular, we describe a method for performing Hensel lifting which avoids "big integer" arithmetic except in very large cases. We compare various factor coefficient bounds, and give examples to show that no one bound is better than all the others. Various devices, some old and some new, to expedite the recombination phase are discussed, and a recommendation is made. Finally, a new family of "pathological" cases is described for which the recombination phase remains very costly. BibTeX, dvi |
|
Massimo Caboara Optimization of basic algorithms In Commutative Algebra PhD Thesis BibTeX, dvi |
|
Massimo Caboara, Eva Riccomagno An algebraic computational approach to the identifiability of Fourier Models Computer algebra and in particular Gröbner bases is a powerful tool in the analysis of designed experiment. This paper applies this algebraic methodology to the identifiability of Fourier models. The choice of the class of trigonometric models forces one to deal with complex entities and algebraic irrational numbers. By means of standard techniques we have implemented a version of the Buchberger algorithm that computes Gröbner bases over the complex rational numbers or other simple algebraic extension of the rational. Some examples are fully carried out. BibTeX |
|
Massimo Caboara, Carlo Traverso Efficient algorithms for ideal operations In this paper we review the known algorithms for performing the basic algorithms for ideal and submodule operations: intersection, transporter and saturation. The algorithms known in the literature for these operations on polynomial rings fall largely into two classes: syzygy algorithms and elimination algorithms. We show that the two classes substantially coincide: they can be seen at most as variants of the same algorithm. We show moreover that these algorithms can be generalized to another algorithm, a module elimination algorithm, that allows the use of a Hilbert function driven algorithm and that, with this feature, appears to be the most efficient algorithm in this class. We give some examples that support this assertion. Because of space constraints we skip all the proofs, that will appear in a full paper together with more exhaustive experiments. BibTeX |
|
Antonio Capani, Gianfranco Niesi The CoCoA 3 Framework for a Family of Buchberger-like Algorithms In this paper we report how we have implemented in release 3.3 of the system CoCoA algorithms for computing Gröbner bases, syzygies, and minimal free resolution of submodules of finitely generated free modules over polynomial rings. In particular we describe the environment we have built where these algorithms are obtained as special instances of a single parametrized algorithm. The outcome is a framework which offers not only efficiency in computing, but also efficiency in designing new algorithms; moreover, it allows the user to interactively execute the above computations, and easily customize the way they are carried out. BibTeX |
|
Lorenzo Robbiano Gröbner Bases and Statistic This survey describes how to use methods of Algebraic Geometry and Commutative Algebra to study some problems arising in Design of Experiments, a branch of Statistics. Contents
BibTeX, dvi |
|
Lorenzo Robbiano, Maria Piera Rogantin Full Factorial Designs and Distracted Fractions Design of Experiments is an important branch of Statistics. One of its key problems is to find minimal Fractions of a Full Factorial Design, which identify a Complete Polynomial Model. This paper shows how to use Computer Algebra and Commutative Algebra techniques and results to produce good classes of solutions to the problem. It is known that most of them can be obtained by means of Gröbner bases, hence they generally depend on the term-order chosen; here we show how to use the so called Distracted Fractions to yield solutions independent of the term-order. BibTeX |
|
Lorenzo Robbiano, Moss Sweedler Ideal and Subalgebra Coefficients For an ideal or K-subalgebra E of K[X1,...,Xn] consider subfields k of K, where E is generated -- as ideal or K-subalgebra -- by polynomials in k[X1,...,Xn]. It is a standard result for ideals that there is a smallest such k. We give an algorithm to find it. We also prove that there is a smallest such k for K-subalgebras. The ideal results use reduced Gröbner bases. For the subalgebra results we develop and then use subduced SAGBI (bases), the analog to reduced Gröbner bases. BibTeX, dvi |
|
Lorenzo Robbiano, Giuseppe Valla Hilbert Poincaré Series of Bigraded Algebras The aim of this paper is to describe some new techniques for computing Hilbert-Poincaré series (HP-series) of standard algebras which can be viewed as subrings of bigraded algebras. In particular, we show how to compute in a uniform way the HP-series of powers of a homogeneous ideal. We also show how to compute HP-series of Segre products and of some Blow-up algebras which are of interest in Algebraic Geometry. For some classes we are able to describe explicit formulas, while for others we prove that there is an algorithm which computes the HP-series directly, without computing the generating equations. BibTeX, dvi |
|
Anna M. Bigatti Computation of Hilbert-Poincaré Series We describe a new algorithm for computing standard and multi-graded Hilbert-Poincaré series of a monomial ideal. We compare it with different strategies along with implementation details and timing data. BibTeX, dvi |
|
Anna M. Bigatti, Lorenzo Robbiano Borel Sets and Sectional Matrices Following the path trodden by several authors along the border between Algebraic Geometry and Algebraic Combinatorics, we present some new results on the combinatorial structure of Borel ideals. This enables us to prove theorems on the shape of the sectional matrix of a homogeneous ideal, which is a new invariant stronger than the Hilbert function. BibTeX, dvi |
|
Massimo Caboara, Pasqualina Conti, Carlo Traverso Yet Another Algorithm for Ideal Decomposition In this paper we describe algorithms to compute equidimensional decompositions of an ideal I of a polynomial ring. The decompositions that we can compute are either faithful , i.e. the intersection of the components is the ideal itself, reduced , i.e. the components coincide with their radical, and their intersection is the radical of I, or iso-radical. The algorithms do not require change of coordinates, nor lexicographical Gröbner bases and GCD on algebraic extensions, and are based on projections in codimension 1 and flatness analysis. In our algorithms there are several points where an arbitrary choices are required. In our experience, smart choice strategies offer a substantial performance improvement. We report a series of experiments both with semi-automatic computations and with an experimental implementation in CoCoA. They seem to support the claim that the algorithm for reduced decomposition, with smart choice strategies, is much more efficient than the Eisenbud-Huneke-Vasconcelos algorithm for the radical implemented in Macaulay, since the range of problems that we are able to solve seems to be far larger. BibTeX |
|
Massimo Caboara, Lorenzo Robbiano Families of Ideals in Statistics In this paper we use Gröbner basis theory and some methods of Algebraic Geometry to solve a relevant problem in Statistics, more specifically in the Design of Experiments. Namely suppose we are given a Full Factorial Design D and a complete polynomial model P, whose support is contained in the order ideal of monomials defined by D. We show how to construct families of ideals defining Fractions F of D which are minimally identified by P. BibTeX |
|
Antonio Capani, Gabriel De Dominicis, Gianfranco Niesi, Lorenzo Robbiano Computing Minimal Finite Free Resolutions In this paper we address the basic problem of computing Minimal Finite Free Resolutions of homogeneous submodules of graded free modules over polynomial rings. We develop a strategy, which keeps the resolution minimal at every step. Among the relevant benefits is a marked saving of time, as the first reported experiments in CoCoA show. The algorithm has been optimized using a variety of techniques, such as minimalizing the number of critical pairs and employing an ad hoc Hilbert-Driven strategy. The algorithm can also take advantage of various a priori pieces of information, such as the knowledge of the Castelnuovo regularity. BibTeX |
|
Massimo Caboara, Gabriel De Dominicis, Lorenzo Robbiano Multigraded Hilbert Functions and Buchberger Algorithm In this paper we describe an algorithm which allows to drive the classical Buchberger Algorithm by means of multigraded Hilbert-Poincaré series. The result is that in the multigraded case one can kill many more useless critical pairs. Besides, the new algorithm, called MGHDriven, is intrinsically parallelizable and it is now implemented in CoCoA BibTeX |
|
Antonio Capani, Gabriel De Dominicis Web Algebra In this paper we propose a model for a general interface between people and Computer Algebra Systems (CAS). The main features in our CAS interface are data navigation and the possibility of accessing powerful remote machines. Our model is based on the idea of Session Management. We implemented our model using the client-server capabilities offered by WWW. We envision our proposal as being useful for: educational purposes; computing; data navigation; communication of structured data; simulation of operations on distributed systems. BibTeX |
|
Antonio Capani, Gianfranco Niesi, Lorenzo Robbiano Some Features of CoCoA 3 CoCoA is a special-purpose system for doing Computations in Commutative Algebra. It is the ongoing product of a research team in Computer Algebra at the University of Genova (Italy), whose members are: Lorenzo Robbiano (team manager), Gianfranco Niesi, Antonio Capani (CoCoA authors), Anna Bigatti, Massimo Caboara, Gabriel De Dominicis and occasionally other researchers and students. BibTeX, dvi |
|
Anna M. Bigatti Aspetti Combinatorici e Computazionali dell'Algebra Commutativa In this thesis (written in Italian) some fundamental aspects of Commutative Algebra are analysed from both the combinatorial and the computational points of view. It consists of three parts:
BibTeX, dvi |
| COCOA's Home | cocoa at dima.unige.it | Last Modified 21 May 2008 |