Research Team in Genova
  commutative and computer algebra 
COCOA's Home cocoa at dima.unige.it Last Modified: 12 October 2010



Maria Laura Torrente
Applications of Algebra in the Oil Industry

PhD Thesis


John Abbott
Challenges in Computational Commutative Algebra

In this paper we consider a number of challenges from the point of view of the CoCoA project 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.
John Abbott
The Design of CoCoALib

This document describes some of the more important design features of CoCoALib, a C++ library for computations in commutative algebra with particular focus on Gröbner bases. For almost 20 years the CoCoA project 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 project, and is the part we shall look at most closely. The software is to be free in the sense of the GPL.


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 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


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.
BibTeX, dvi, CoCoA code



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, CoCoA code, CoCoA code


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.
BibTeX, dvi

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.
BibTeX, dvi

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:
  • Introduction
  • Zero-Dimensional Ideals and Commuting Endomorphisms
  • Zero-Dimensional Ideals and Rewrite Rules

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, 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, CoCoA code
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.


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.
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.
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.
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.
  1. Introduction
  2. From Design of Experiments to Commutative Algebra
  3. Computing Confounding Polynomials: the Buchberger-Möller Algorithm
  4. Identifying the Models
  5. Some Problems
    Problem 1: Given a Fraction, what are the Models identifiable by it?
    Problem 2: Given a Model, what are the Fractions which identify it?
    Problem 3: Which Fractions identify the highest (lowest) number of Models?
  6. Concluding Remarks

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.
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.
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.
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.


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
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.
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:
  • Part 1 contains useful definitions and theorems in Commutative Algebra
  • Part 2 is devoted to the combinatorial aspects, and in particular extends the paper (Bigatti93) Upper Bounds for the Betti Numbers of a Given Hilbert Function. It starts by proving some theorems on Borel and lex-segment sets, and then generalises these to the case of homogeneous ideals thereby giving new elementary proofs for the theorems of Gotzmann and Green.
  • Part 3 is devoted to the computational aspects, and is available in English as the paper (Bigatti97) Computation of Hilbert-Poincaré Series

BibTeX, dvi

*This page was generated by CoCoA
COCOA's Home cocoa at dima.unige.it Last Modified 12 October 2010