The Design of the CoCoA 3 System

SummaryThe thesis consists of six chapters organized as follows.In Chapter 1 we present an introduction to the eld of the Computer Algebra. After fewhistorical notes we introduce the Symbolic Computation and its relation to the ComputerAlgebra. The chapter contains also an introduction to the Grobner Bases.In Chapter 2 we describe the CoCoA system both from the user point of view and fromthe architectural point of view. In particular it is presented CoCoAL, the high level lan-guage of the system, and the decomposition of the architecture in its main modules; thedescription of the architecture presents also how we solved the problem of the portabilityby means of the combination of CTL,alow level intermediate language and the CDevices,an abstraction of the phisical devices.In Chapter 3 we present the Grobner Framework, an advanced tool for doing computationsbased on an Generalization of the Buchberger Algorithm. In brief the framework consistsof a parametrization of the Buchberger Algorithm with some parameter functions and theinstantiation of the algorithm by using dierent implementation of these parameters.In Chapter 4 we explain howwehave used the Grobner Framework for solving the problemof computing Minimal Finite Free Resolutions of homogeneous submodules of graded freemodules over polynomial rings.In Chapter 5 it is introduced EEE, an new advanced representation for polynomials whichexhibits both great compactness of space and good performance. This new polynomialrepresentation was inspired by the mathematical structure intrinsic in homogeneous prob-lems, and consists of a parametrized family of representations allowing varying degreesof trade-o between space and time. Its compactness also makes EEE interesting as aprotocol for communicating polynomials.Finally the Chapter 6 contains the presentation of the Session Management Framework,which is a general approach for accessing computing systems in an interactive Web-basedenvironment. SMF is based on the concept of Session which is a list of Queries. Each queryis characterized by an Input and an Output. The user writes requests to query inputs andthen submits the query to an agent, which put the answer in the output eld of the query.The framework gives the necessary abstraction from the locality of the sessions and as suchpermits to write tools for interacting with a computing system from remote clients (e.g.Web browsers).
5
Chapter 1Introduction to the ComputerAlgebraRecently there has been the publication of the book \Commutative Algebra with a viewtoward algebraic geometry" [Eis95]. byDavid Eisenbud. Because of the importance of theauthor this book has already become a standard reference, in particular for the commu-tative algebraist and for the algebraic geometer. The book contains a chapter about theGrobner bases and the related computational aspects of algebra. An eminent algebraicgeometer, Marc Green, in the review of this book writes textually:There is one change which has overtaken commutative algebra that is in myview revolutionary in character { the advent of symbolic computation. Thisis as yet an unnished revolution. At present, many researchers routinely useMacaulay, Maple, Mathematica, and CoCoA to perform computer experiments,and as more people become adept at doing this, the list of theorems that havegrown out of such experiments will enlarge. The next phase of this devel-opment, in which the questions that are considered interesting are in
uencedby computation and where these questions make contact with the real world,is just beginning to unfold. I suspect that ultimately there will be a sizableapplied wing to commutative algebra, which now exists in embryonic form.1.1 Historical NotesThe birth and growth of algebra and of algorithms are stricly related. The origins ofboth disciplines go back to Muhammed ibn-Musa al-Khwarizmi al-Quturbulli, who was an6
important person at the court of the Calif Al-Mamun of the Abassid dynasty in Baghdad(813-833 d.C.).He merged the axiomatic mathematics of the Greeks with the algorithmic mathematicsof the Hindus, making popular decimal representation, symbolic calculation, etc. Hisbook \al-Jabr wal-Muqabala" originated the terms algebra (as a distortion of al-Jabr) andalgorithm (distortion of al-Khwarizmi).The two topics developed at dierent speeds in dierent communities. The discipline ofalgorithms remained frozen for years, whilst the discipline of algebra grew at as surprisingspeed.In the last century there were the theoretical-functional and the topological approach byRiemann, the more geometrical approach by Brill and Noether, and the purely algebraicapproach of Kronecker, Dedekind e Weber. The discipline was further enriched with thework of important algebrist and algebraic geometers (like Newton, Eulero, Jacobi, Noether,Castelnuovo, Macaulay, Hilbert, and a lot of others).But soon algebra lost its constructive foundations and rose as a calculation tool. Forexample the in
uence of the school of Bourbaki mined the reputation of the beautiful andconstructive theory of the elimination,developed in more than half a century by Sylvester,Kronecker, Mertens, Konig, Hurwitz e Macaulay.The revival of the constructive algebra is a rather recent phenomenon and gained particularbenet from the work of Tarski, Seidenberg, Ritt, Collins, Hironaka, Buchberger, Bishop,Richman, and others.Here is what Hensel writes in the preface to the lectures on the Kronecker's number theory.
[Kronecker] believed that one could, and that one must, in these parts of mathe-matics, frame each denition in suchaway that one can test in a nite numberof steps whether it applies to any given quantity. In the same way, a proofof the existence of a quantity can only be regarded as fully rigorous when itcontains a method by which the quantity whose existence is to be proved canactually be found.Even though for many years there was a large interest in automation of the computationprocess, the lackofmodern computers discouraged the study of algoriths.Around the 1670 Gotted Leibnitz invented the well known Leibnitz wheel capable ofperforming the four operations. Moreover Leibnitz proposed the characteristica generalis,asymbolic language for the translation of the methods and the assertions of mathematicsin algorithms and formulas.In the XIX century Charles Babbage devised, but never built, a powerful computation7
machine, the analytical engine, capable of manipulating problems in algebra and math-ematical analysis. Babbage, referring to his machine, said: \it could do everything butcompose country dances" [HH80].During this century two events gave oxigen to this sector: the rst was the study ofthe foundations of mathematics, as stated in the Hilbert program; the result where theincompleteness theorems of Godel, the computational models of Church, Turing, Markov,and Post, and the, existence of a \universal" machine and the computability problem. Thesecond event was the birth of modern computers after the end of World War Two.Initially the problems managed by computers were purely numerical, but soon it becameclear that machines were also able to perform operations with symbolic data.It is interesting to note that since 1844 this aspect of computers was already clear in themind of the countess Lady Ada Augusta Lovelace. Here is what she wrote about the abilityof Babbage's machine [HH80].Many persons who are not conversant with mathematical studies imagine thatbecause the business of [Babbage's analytical engine] is to give its results innumerical notation, the nature of its process must consequently be aritmeticalrather than algebraic and analytical. This is an error. The engine can arrangeand combine its numerical quantities exactly as if they were letters or anyother general symbols; and, in fact, it might bring out its results in algebraicnotation. . .The creation of general purpose programming languages (Post, Chomsky,Backus, Church),and in particular the Lisp language, made it possible for Nolan of M.I.T. and Kahrimanianof Temple University, to develop in 1953 the very rst symbolic computing systems.1.2 Symbolic Computing and Computer Algebra1.2.1 Symbolic ComputingNowadays the Symbolic Computing is a eld which grows rapidly within the frontier be-tween mathematics and computer science. On one hand formalistic mathematics appearedto be limited if a method which uses existence theorems is preferred to a more construc-tive approach; on the other hand the numerical techniques, very useful in linear problems,collided with relevant obstacles due to the bigger complexityofnonlinear problems.On the computer science side the development of new methodologies and computing meth-ods, together with the growth of computing power and felling of costs, permitted in the8
last years the diusion of computing techniques that were considered interesting only fromthe theoretical point of view. Moreover algebraic-geometrical methods revealed to be apowerful aid in various technological applications (signal processing, code theory, cryp-tography, geometric modelling, CAD, etc.) and showed multiple benets in the elds ofbiology,chemistry, physics, and robotics.From the mathematical pointofviewit is possible today to access computation exampleswhich, for the level of complexity,arevery far from the possibilities of manual computation;and as a consequence it is possible to experiment in depth with various mathematicalstructures.The researcher is now able to formulate with a great precision conjectures which in thepast could not be expressed, because it was impossible even to enunciate them.Mathematicians are now interested in creating more sophisticated symbolic computationtools in order to further explore the eld, the target in mind being to expose the propertiesfor which there is a reasonable \experimental evidence".Franz Winkler wrote in his book \Polinomial Algorithms in computer algebra" [Win96]:By the aid of computer algebra the capacity for mathematical problem solvinghas been decisively improved.Another interesting aspect is the possible interaction between algebraic computation andnumerical computation, as again Winkler said [Win96]:Both forms of scientic computation have their merits and they should be com-bined in a computational environment... Often it is more economical in termsof computation time to simplify an expression algebraically before evaluatingit numerically. In this way the expression becomes simpler and less prone tonumerical errors.1.2.2 Constructive Algebra, Computer Algebra e IntuitionismEdwards summarized the Kronecker's point of view about the Constructive Algebra asfollows [Edw89]:Kronecker believed that a mathematical concept was not well dened until youhad shown how, in each specic instance, to decide [algorithmically] whetherthe denition was fullled or not. 9
One motivation for the study of constructive algebra is the following: it enriches anddeepens the classical algebra. If we try to make constructive a theorem, we have to studyin detail the structure of the examined object; the result of this study may furnish usefulinformation for the implementation of eÆcient algorithms.An eminent algebraic geometer who preferred the algorithmic point of view is Abhyankar.He strongly opposed the non-constructive approach, stressing the importance of construc-tive theories, for example elimination theory. His point of view is obvious from one of hishumorous poetries, which begins... [Mis93]:Polynomials and power series.May they forever rule the world.Eliminate, eliminate, eliminate.Eliminate the eliminators of elimination theory.The computer theoretician extends Abhyankar's point of view to the extreme limit: heregards the existence of a construction as a rst step for the classication of computationalcomplexity, which is inherent to the algebraic problem. It was within general ambit ofSimbolic Computing, and based upon the constructive approach, a new discipline began:Computer Algebra.Here is what Bhubaneswar Mishra says in his book \Algorithmic Algebra" [Mis93]:The eld of computational algebra ...is a relative newcomer, but holds thepromise of adding a new dimension to the subject of algorithms. After a mil-lennium, it appears that the subject of algorithms and algebra may nallyconverge and coexist in a fruitful symbiosis.Thomas Becker e Volker Weispfenning, in their book \Grobner bases: A ComputationalApproach to Commutative Algebra" [BW93] wrote:The development of new concepts and results in the area has now establishedcomputer algebra as an independent discipline that extends deeply into bothmathematics and computer science.Computer Algebra is not to be confused with the intuitionism, even if the relationshipsbetween these terms are really strong. Here is a passage from a conference held by CarloTraverso during the occasion of the XIII U.M.I. (Union of the Italian Mathematicians)Congress [Tra88]: 10
If we want to reduce the intuitionism to a slogan, we may say the following: aformula of the type 8x9y:p(x; y) means that exists an algorithm which has aninput x, an output y and a proof of p(x; y). The proof, in order to be valid, mustdemonstrate that the algorithm terminates, and this (8x9n 2 N such that inn steps the algorithm terminates) has to be intuitionist, that is it must containan explicity procedure to determine the number of the steps starting from thedata; in other words it is an estimation of the complexity of the algorithm.The emphasis of the Computer Algebra is on the algorithms even more thanfor the intuitionism, but the notion of algorithm is dierent: not only are con-sidered the algorithms with an complexity estimation, but also the algorithmsfor which it is possible to demonstrate the termination in a non constructivemanner; for sure any convergence estimation is welcome, but such estimationmay be given by means of a proof, or by a probabilistic estimation, or simplyby a statistics. Any proof method is good as long as it is given in a formal way.1.2.3 Grobner BasesDuring the recent history of these modern disciplines there was a fundamental event, thebirth of the Grobner bases. There are a lot of people who claim for the paternity of thisnotion, and in fact there were a lot of precursors; as a matter of fact a central work was theone made by Bruno Buchberger, who, in his PhD thesis in 1965 [B65] introduced the notionof Grobner basis and described an algorithm for its computation, the famous \'BuchbergerAlgorithm".Wecansay that the theory of the Grobner bases consists on one hand on the generalizationto the multivariate case of the Euclidean algorithm for the computation of the greatestcommon divisor between two univariate polynomials; on the other hand it consists of thegeneralization to the polynomial case of the Gaussian reduction for the solution of linearequations systems.Thomas Becker and Volker Weispfenning in their book \Grobner bases: A ComputationalApproach to Commutative Algebra" wrote [BW93]:There is one particular contribution made by computational algebra that is inmost dire need of being introduced in the mathematical mainstream, namely,the theory of Grobner bases.David Cox, John Little, and Donald O'Shea on the foreward of their book \Ideals, Varietiesand Algorithms" wrote, [CLD92]: 11
In the 1960's, Buchberger and Hironaka discovered new algoriths for manipulat-ing systems of polynomial equations. Fueled by the development of computersfast enough to run these algorithms, the last two decades have seen a minorrevolution in commutative algebra. The ability to compute eÆciently withpolynomial equations has made it possible to investigate complicated examplesthat would be impossible to do by hand, and has changed the practice of muchresearch in algebraic geometry. This has also enhanced the importance of thesubject for computer scientists and engineers, who have begun to use thesetechniques in a whole range of problems.Some importants papers among like [Rob86] and [MM86] consolidated, in the middle ofthe '80, the mathematical foundations of the Grobner bases and of some related notions.Here is what Lorenzo Robbiano wrote in the review [Rob96] of the books \Grobner Bases:A computational approachtocommutative algebra", byBecker and Weispfenning [BW93],and \An introduction to Grobner Bases" by Adams and Loustaunau [AL94]:For manyyears the importance of Buchberger's work was not fully appreciated.Only in the eighties did researchers in mathematics and computer science startadeepinvestigation of the wide variety of application that could be developedfrom the new theory. Many generalizations and applications to dierent prob-lems were investigated. It immediately became clear that the theory of GrobnerBases was about to become widely used and immensely populare in many areasof science. What I have not yet said, but what is rather starling, is the uttersimplicity of the fundamental ideas. Simplicity and power: two ingredients thatmake a perfect mix for the success of a theory.1.3 The Problem of the RepresentationKronecker once said:God created integers: the rest is human's stu.Anyway the man has problems even with the representation of integers! The majority ofprogramming languages treat integers as a nite set, such as f231;:::;231  1g. It's easyto say: \My data is small, hence the answer will be small, so I do not need big integersand this set will suÆce. This assertion is completely wrong. Suppose you want to computethe GCD (greatest common divisor), of the following two polynomials ([Knu69, Bro71]):12
A(x)=x8 + x6  3x4  3x3 +8x2 +2x 5B(x)=3x6 +5x4  4x2  9x+21By using the well known Euclidean algorithm it is easy to see that the last computedinteger has 35 digits (117 bits!), even if the input has small coeÆcients and the outputconsists of the result 1 (the two polynomials are coprime).In the book \Computer Algebra: Systems and Algorithms for Algebraic Computation" byDavenport, Siret, Tournier [DST88] you nd:
[The problem] of the \intermediate expression swell" is one of the biggest prob-lems in Computer Algebra.1.3.1 Representation of PolynomialsIn the eld of Commutative Algebra the problem of having a good representation of mul-tivariate polynomials is of fundamental importance.The two main points to consider are: the representation of the coeÆcients and the repre-sentation of the support of polynomials, independently of the format of the coeÆcients.The support is the set of the power products of the terms whose coeÆcients is not null.Representation of CoeÆcientsComputing with variable sized coeÆcients implies the use of dierent strategies: the coef-cients in Zp have a xed size as the 
oating points and hence the computational cost ofthe operations on the coeÆcients is constant.An interesting point is to ask if it is better to keep the polynomials monic (i.e. with theleading coeÆcient 1) or not; in the case of Zp the overhead is not considerable and hencemay be useful to keep the polynomials monic; on the contrary on Q the cost of dividingby the leading coeÆcient is very high and hence it is important to adopt an alternativerepresentation, liketheones proposed in [GPT88].Representation of the SupportLets start by considering the univariate polynomials. A rst distinction is between thedense and the sparse representation. A representation is said to be sparse if the terms with13