CoCoA: A System for Computations in Commutative Algebra

Abstract

CoCoA is a special-purpose system for doing Computations in Commutative Algebra. It runs on all common platforms.

CoCoA's particular strengths include ideal/module operations (such as Gröbner bases, syzygies and minimal free resolutions, intersections, divisions, the radical of an ideal, etc), polynomial factorization, exact linear algebra, computing Hilbert functions, and computing with zero-dimensional schemes and toric ideals.

The usefulness of these technical skills is enhanced by the mathematically natural language for describing computations. This language is readily learned by students, and enables researchers to explore and develop new algorithms without the administrative tedium necessary when using "low-level" languages.

Lately the CoCoA project has entered a new phase: the new design is expressly developed as a C++ library; a server and a standalone interactive system will be built on top of this library. The design should reflect the underlying mathematical structure since this will ensure that the library is natural to use.

In this tutorial we will show several applications of Computer Commutative Algebra through the use of CoCoA and CoCoALib.

Triangular Decompositions of Polynomial Systems: from Theory to Practice

Abstract

Triangular decompositions are one of the major tools for solving polynomial systems. For systems of algebraic equations, they provide a convenient way to describe complex solutions and a step toward isolation of real roots or decomposition into irreducible components. Combined with other techniques, they are used for these purposes by several computer algebra systems. For systems of partial differential equations, they provide the main practicable way for determining a symbolic description of the solution set. Moreover, thanks to Rosenfeld's Lemma, techniques from the algebraic case apply to the differential one [BLOP95].

Theory

The concept of a characteristic set, introduced by Ritt [Ritt32], is the cornerstone of the theory. He described an algorithm for solving polynomial systems by factoring in field extensions and computing characteristic sets of prime ideals. Wu [Wu87] obtained a factor-free adaptation of Ritt's algorithm. Several authors continued and improved Wu's approach: among them Chou, Gao [ChGa92], Gallo, Mishra [GM90] Wang [Wang93b]. Considering characteristic sets of non-prime ideals leads to difficulties that were overcome by Kalkbrener [Kalk91] and, Yang and Zhang [YaZh94] who defined particular characteristic sets, called regular chains. See also the work of Lazard and his students [ALM97]. The first part of this tutorial will be an introduction to this notion for a general audience.

Algorithms

Regular chains, combined with the D5 Principle [D5] and a notion of polynomial GCD [Moreno00], have also contributed to improve the efficiency of algorithms for computing triangular decompositions, as reported in [PAMMM97b]. To go further, complexity estimates of the output regular chains were needed. Such results were provided by Dahan and Schost [DaSc04]. Together with the notion of equiprojectable decomposition, they have brought the first modular algorithm for computing triangular decompositions [DMSWX05a]. The second part of this tutorial will focus on polynomial GCDs modulo regular chains. Using the RegularChains library [LeMoXi05] in Maple, we show how they are used for producing equiprojectable decompositions.

Implementation

This is certainly the hot topic today. Obtaining fast algorithms for the low-level routines used in triangular decompositions [DMSX06] and developing implementation techniques for them [FLMS06] are the priorities that we shall discuss in the last part of this tutorial.

References

[ALM97]

P. Aubry, D. Lazard, and M. Moreno Maza. On the theories of triangular sets. J. Symb. Comp., 28(1-2):105-124, 1999.

[PAMMM97b]

P. Aubry and M. Moreno Maza. Triangular sets for solving polynomial systems: A comparative implementation of four methods. J. Symb. Comp., 28(1-2):125-154, 1999.

[BLOP95]

F. Boulier, D. Lazard, F. Ollivier, and M. Petitot. Representation for the radical of a finitely generated differential ideal. In Proc. of ISSAC'95, pp. 158-166, 1995.

[ChGa92]

S.C. Chou and X.S. Gao. Solving parametric algebraic systems. In Proc. ISSAC'92, pp. 335-341, Berkeley, California, 1992.

[DMSWX05a]

X. Dahan, M. Moreno Maza, É. Schost, W. Wu, and Y. Xie. Lifting techniques for triangular decompositions. In Proc. ISSAC'05} pp. 108-115. ACM Press, 2005.

[DMSX06]

X. Dahan, M. Moreno Maza, É. Schost, and Y. Xie. On the complexity of the D5 principle. In Proc. of Transgressive Computing 2006, Granada, Spain, 2006.

[DaSc04]

X. Dahan and É. Schost. Sharp estimates for triangular sets. In Proc.ISSAC 04, pp. 103-110. ACM, 2004.

[D5]

J. Della Dora, C. Dicrescenzo, and D. Duval. About a new method for computing in algebraic number fields. In Proc. EUROCAL 85 Vol. 2, volume 204 of Lect. Notes in Comp. Sci., pp. 289-290. Springer-Verlag, 1985.

[FLMS06]

A. Filatei, X. Li, M. Moreno Maza, and É. Schost. Implementation techniques for fast polynomial arithmetic in a high-level programming environment. In Proc. ISSAC'06. ACM Press, 2006.

[GM90]

G. Gallo and B. Mishra. Efficient algorithms and bounds for Wu-Ritt characteristic sets. In Proc. MEGA'90, pp. 119-142, 1990.

[Kalk91]

M. Kalkbrener. Three contributions to elimination theory. PhD thesis, Johannes Kepler University, Linz, 1991.

[LeMoXi05]

F. Lemaire, M. Moreno Maza, and Y. Xie. The RegularChains library. In Ilias S. Kotsireas, editor, Maple Conference 2005, pp. 355-368, 2005.

[Moreno00]

M. Moreno Maza. On triangular decompositions of algebraic varieties. Technical Report TR 4/99, NAG Ltd, Oxford, UK, 1999. http://www.csd.uwo.ca/~moreno.

[Ritt32]

J. F. Ritt. Differential Equations from an Algebraic Standpoint, volume 14. American Mathematical Society, New York, 1932.

[Wang93b]

D. M. Wang. An elimination method for polynomial systems. J. Symb. Comp., 16:83-114, 1993.

[Wu87]

W. T. Wu. A zero structure theorem for polynomial equations solving. MM Research Preprints, 1:2-12, 1987.

[YaZh94]

L. Yang and J. Zhang. Searching dependency between algebraic equations: an algorithm applied to automated reasoning. In J. Johnson, S. McKee, and A. Vella, editors, Artificial intelligence in mathematics. Oxford University Press, 1994.

Hybrid Symbolic-Numeric Computation

Abstract

Several standard problems in symbolic computation, such as greatest common divisor and factorization of polynomials, sparse interpolation, or computing solutions to overdetermined systems of polynomial equations have non-trivial solutions only if the input coefficients satisfy certain algebraic constraints. Errors in the coefficients due to floating point round-off or through physical measurement thus render the exact symbolic algorithms unusable. By symbolic-numeric methods one computes minimal deformations of the coefficients that yield non-trivial results. We will present hybrid algorithms and benchmark computations based on Gauss-Newton optimization, singular value decomposition (SVD) and structure-preserving total least squares (STLS) fitting for several of the above problems.

A significant body of results to solve those "approximate computer algebra" problems has been discovered in the past 10 years. In the Computer Algebra Handbook the section on "Hybrid Methods" concludes as follows [GKW03]:

The challenge of hybrid symbolic-numeric algorithms is to explore the effects of imprecision, discontinuity, and algorithmic complexity by applying mathematical optimization, perturbation theory, and inexact arithmetic and other tools in order to solve mathematical problems that today are not solvable by numerical or symbolic methods alone.

Approximate Greatest Common Divisors [KYZ06]

Our paper at this conference presents a solution to the approximate GCD problem for several multivariate polynomials with real or complex coefficients. In addition, the coefficients of the minimally deformed input coefficients can be linearly constrained. In our tutorial we will give a precise definition of the approximate polynomial GCD problem and we will present techniques based on parametric optimization (slow) and STLS or Gauss/Newton iteration (fast) for its numerical solution. The fast methods can compute globally optimal solutions, but they cannot verify global optimality. We show how to apply the constrained approximate GCD problem to computing the nearest singular polynomial with a root of multiplicity at least k ≥ 2.

Approximate Factorization of Multivariate Polynomials [GKMYZ04]

Our solution and implementation of the approximate factorization problem follows our approach for the approximate GCD problem. Our algorithms are based on a generalization of the differential forms introduced by W. Ruppert and S. Gao to many variables, and use SVD or STLS and Gauss/Newton optimization to numerically compute the approximate multivariate factors.

Solutions of Zero-dimensional Polynomial Systems [RTZ03]

We translate a system of polynomials into a system of linear partial differential equations (PDEs) with constant coefficients. The PDEs are brought to an involutive form by symbolic prolongations and numeric projections via SVD. The solutions of the polynomial system are obtained by solving an eigen-problem constructed from the null spaces of the involutive system and its geometric projections.

References

[GKMYZ04]

Gao, S., Kaltofen, E., May, J. P., Yang, Z., and Zhi, L. Approximate factorization of multivariate polynomials via differential equations. In Gutierrez, J., Ed. ISSAC 2004 Proc. 2004 Internat. Symp. Symbolic Algebraic Comput. (New York, N. Y., 2004), ACM Press, pp. 167-174.

[GKW03]

Grabmeier, J., Kaltofen, E., and Weispfenning, V., Computer Algebra Handbook. Springer Verlag, 2003, pp. 109-124.

[KYZ06]

Kaltofen, E., Yang, Z., and Zhi, L., Approximate greatest common divisors of several polynomials with linearly constrained coefficients and singular polynomials. In ISSAC 2006 Proc. 2006 Internat. Symp. Symbolic Algebraic Comput. (New York, N. Y., 2006), Jean-Guillaume Dumas, Ed., ACM Press.

[RTZ03]

Reid, G., J.Tang, and Zhi, L., A complete symbolic-numeric linear method for camera pose determination. In Sendra, J., Ed. ISSAC 2003 Proc. 2003 Internat. Symp. Symbolic Algebraic Comput. (New York, N.Y., 2003). ACM Press, pp. 215-223.

Acknowledgement

This research was supported in part by the National Science Foundation of the USA under Grants CCR-0305314 and CCF-0514585 (Kaltofen) and OISE-0456285 (Kaltofen, Yang and Zhi). This research was partially supported by NKBRPC (2004CB318000) and the Chinese National Natural Science Foundation under Grant 10401035 (Yang and Zhi).