Symbolic Computation: Pure Computer Mathematics

Bruno Buchberger RISC-LINZ —

Research Institute for Symbolic Computation

Johannes Kepler University, A4040 Linz, Austria (Europe)

Tel: +43 (7236) 3231-41, Fax: +43 (7236) 3338-30

                          Bitnet: k313370 at aearn

—

October 22, 1993

Abstract

This paper is a survey on Symbolic Computation. We first propose a new definition of the term “Symbolic Computation”: Symbolic Computation is computation with objects that are “symbolic” in the sense that they are finite representations (symbols) for infinite, abstract ojects in the domains of pure mathematics. In the second part of the paper we summarize the facilities available in modern symbolic computation software systems. In the third part we give some examples of recent mathematical research results on which improved symbolic computation algorithms can be based. Finally, we compile the most important literature and software systems references for encouraging newcomers to access these powerful new problem solving techniques.

The main message of this paper is twofold:

• Applied mathematicians are encouraged to experiment with the available Symbolic Computation software systems and, by doing so, will experience an enormous expansion of their problem solving potential.

• Pure mathematicians are encouraged to consider the “algorithmization” of their respective field of interest and will experience the enormous intellectual and mathematical challenge of such a project that often goes far beyond the degree of difficulty found in “traditional” pure mathematics.

1 A New Definition of Symbolic Computation

Pragmatically, one could “define” Symbolic Computation (symbolic mathematics, computer algebra, formula manipulation) to encompass everything that is available in present-day symbolic computation systems like MACSYMA, Maple, Mathematica or Scratchpad. Of course, a definition by characterizing properties of the field is more desirable.

Sometimes, Symbolic Computation is simply characterized as “Non-Numerical Computation”. This characterization, however, is too wide. Many non-numerical algorithms, for example, graph theoretical algorithms are not considered to be symbolic. Similarly, a definition that characterizes Symbolic Computation simply as “computation with symbols” is too wide because, for example, word processing considers symbols without having the flavor of symbolic computation.

In an attempt to characterize the flavor of computations in existing “Symbolic Computation” software systems with a view to predict and challenge what should and could be added to theses systems in the future, we believe that the fundamental feature of Symbolic Computation is that

Symbolic Computation = computation with finite (concrete) objects having infinite (abstract) semantics.

Example: The string “sin(2x)” is a finite object. It represents an infinite object, namely, a mathematical function consisting, in terms of set theory, of infinitely many pairs of real numbers. In other words, the symbolic, finite, concrete expression “sin(2x)” has an infinite semantics (meaning) in an abstract domain of mathematics.

Example: The string “((x, y), (2^{8}, 3^{3}))” is a finite object that may be considered as a concise representation of a very complex (“practically infinite”) abstract mathematical object, namely, a finite group with 6912 elements and a 6912 × 6912 multiplication table.

Example: A formula of the theory of real closed fields, for example, ∀a_{0}, a_{1}, a_{2}∃y(x^{3}+ a_{2}x^{2} + a_{1}x + a_{0} = 0) is a finite string object. It says something about infinitely many abstract objects, namely, real numbers. If, by finite manipulation on such finite formula objects, the formula can be proven it says something about an infinite abstract domain, i.e. the formula has an infinite semantics.

Problem solving in Symbolic Computation, then, proceeds in the following steps:

• We want to solve a problem in a domain of infinite, complex finite, “abstract”, objects (a domain of “pure” mathematics).

• We represent (a subset of) these abstract by finite representations (“symbolic” representations).

• We try to solve the problem for the abstract domain by solving, by an algorithm, the corresponding problem for the finite representations.

Example: The famous problem of “symbolic integration” is specified as follows: Given a symbol string s find a symbol string t such that the function represented by t is the anti-derivative of the function represented by s. Note that the problem specification necessarily involves the semantics of the string objects, i.e. the notion “the function represented by ...”.

As a pun, we could also say that

Symbolic Computation = Pure Computer Mathematics

with two possible parsings: Symbolic Computation is computerization of pure mathematics (i.e. mathematics in abtract domains) and Symbolic Computation is computer mathematics in its purest form.

It is a common misunderstanding that

Symbolic Computation = Trivial Mathematics Repeated in Loops on a Computer

and therefore is the domain of “mathematicians” who want to escape the intrinsic difficulties of inventing proofs by, instead, “experimenting” with well-known existing mathematics on examples using computers.

I dare to assert that, rather,

Pure Computer Mathematics typically needs more sophisticated mathematics (i.e. more sophisticated proofs) than Pure Mathematics !

This is so because problem solving in mathematics essentially proceeds by proving theorems that show how a problem can be reduced to other (hopefully easier) problems.

• In Pure Mathematics the problem reduction (proof of the theorem) may involve very powerful, non-algorithmic operators (e.g. “choose an x such that P (x)”).

• In Pure Computer Mathematics (Symbolic Computation) the problem reduction must involve only algorithmic operators (e.g. “while P (x) do x := f(x)”).

Pure Computer Mathematics, therefore, often is more demanding than Pure Mathematics because fewer tools are available in the algorithmic reduction methods of constructive proofs (that can be translated, one-to-one, to computer algorithms).

(On the other hand, one can also argue that Pure Mathematics is more demanding than Pure Computer Mathematics because, by results of algorithm theory, Pure Computer Mathematics can sometimes represent only relatively modest subdomains of the abstract general domains of Pure Mathematics and, thus, the problem reductions of Pure Mathematics are more general and therefore sometimes more difficult.)

Summarizing, • Symbolic Computation is an exciting and challenging future area for pure math-

ematicians from all areas (because more sophisticated proofs are needed).

• Symbolic Computation becomes more and more powerful for all application areas (because the more sophisticated proofs result in “better” problem solving methods).

• Symbolic Computation combines the elegance and “insight” of pure mathematics with the practical efficiency of computer mathematics.

2 Symbolic Computation at Work

In order to be able to assess the practical problem solving power of recent symbolic computation software systems it is best to experiment with at least one of them, typically in interactive mode on a workstation. In the final section of the paper we compile the information necessary to obtain these systems from the academic or professional vendors. Also, it may help to read the papers (Arney et al. 1990) and (Wang 1990) in the same proceedings.

In this section we can only enumerate the most important facilities these systems typically provide.

Arithmetic in Basic Domains: Symbolic computation software systems provide

• “long” integers and rationals,

• high precision floating point numbers,

• other number domains (e.g. finite fields, algebraic number fields),

• basic number theoretic functions (e.g. Extended GCD, Moebius function etc.),

• basic combinatorial function (e.g. Stirling numbers, Bernoulli numbers etc.),

• polys and rational functions,

• classes of orthogonal polys (e.g. Legendre etc.),

• elementary transcendental functions and mathematical constants,

• special functions (e.g. Bessel, Gamma, exponential integral etc.),

• simplification of expressions involving all of the above,

• coercion and transformation between different number domains.

Algebraic Systems: Symbolic computation software systems provide • exact solution of algebraic equations (with symbolic coefficients, multivariate,

higher degree),

• use of equations as “algebraic rules”,

• transformation between various representations of curves and surfaces,

• complete solution to systems of multivariate, non-linear inequalities,

• topologically correct decomposition of n-space w.r.t polynomial inequalities.

Example: The command Reduce[ a x∧2 + b x + c == 0, x] in Mathematica will result in a complete symbolic analysis of the various possible solutions dependent on the values of the parameters a, b, c.

   Example: The command AlgebraicRules[ { a == x + y, b == x y}, {x, y,

a, b}] in Mathematica will result in the set of rewrite rules { - y ∧2 -> b - a y, -x -> -a + y } that completely rewrites any polynomial in x, y in terms of the polynomials a and b, if this is possible, or decides that this is not possible at all. This powerful simplification mechanism is based on the author’s Gröbner bases method, see (Buchberger 1985).

   Example: The command gbasis( [ c1 * c2 - cf * ct * cp + sf * sp, ...],
[sp, st, sf, cp, ct, cf, py, s2, s1, c2, c1] ), where [ c1 * c2 - cf * ct

* cp + sf * sp, ...] is the system of algebraic equations that describes the inverse kinematic of a certain class of robots, produces a fully triangularized version of the system

c_{1}^{2} + \frac{px^{2}}{pz^{2}−2·l_{1}·pz−l_{2}^{2}+l_{1}^{2}} = 0,

c_{2} + \frac{pz^{2}−2·l_{1}·pz−l_{2}^{2}+l_{1}^{2}}{l_{2}} · px · c_{1} = 0, s_{1}^{2} − \frac{pz^{2}−2·l_{1}·pz+px^{2}−l_{2}^{2}+l_{1}^{2}}{pz^{2}−2·l_{1}·pz−l_{2}^{2}+l_{1}^{2}} = 0, s_{2} − \frac{pz−l_{1}}{l_{2}} = 0, py + \frac{pz^{2}−2·l_{1}·pz−l_{2}^{2}+l_{1}^{2}}{px} · c_{1} · s_{1} = 0, cf^{2} − \frac{pz^{2}−2·l_{1}·pz+px^{2}−l_{2}^{2}+l_{1}^{2}}{pz^{2}−2·l_{1}·pz−l_{2}^{2}+l_{1}^{2}} = 0, ct = 0, cp + \frac{pz^{3}−3·l_{1}·pz^{2}−l_{2}^{2}·pz+3·l_{1}^{2}·pz+l_{1}·l_{2}^{2}−l_{1}^{3}}{l_{2}·pz^{2}−2·l_{1}·l_{2}·pz+l_{2}·px^{2}−l_{2}^{3}+l_{1}^{2}·l_{2}} · s_{1} · cf = 0,

sf + \frac{pz^{2}−2·l_{1}·pz−l_{2}^{2}+l_{1}^{2}}{pz^{2}−2·l_{1}·pz+px^{2}−l_{2}^{2}+l_{1}^{2}} · c_{1} · s_{1} · cf = 0,

st + \frac{pz^{2}−2·l_{1}·pz−l_{2}^{2}+l_{1}^{2}}{pz^{2}−2·l_{1}·pz+px^{2}−l_{2}^{2}+l_{1}^{2}} · s_{1} · cf = 0,

sp + \frac{pz^{4}−4·l_{1}·pz^{3}−2·l_{2}^{2}·pz^{2}+6·l_{1}^{2}·pz^{2}+4·l_{1}·l_{2}^{2}·pz−4·l_{1}^{3}·pz+l_{2}^{4}−2·l_{1}^{2}·l_{2}^{2}+l_{1}^{4}}{l_{2}·px·pz^{2}−2·l_{1}·l_{2}·px·pz+l_{2}·px^{3}−l_{2}^{3}·px+l_{1}^{2}·l_{2}·px} · c_{1} · s_{1} · cf = 0.

where the dependent quantities c1, c2, s1, s2, py, cf, ct, cp, sf, st, sp are decoupled and expressed in terms of the independent quantities px, pz and symbolic parameters l1, l2 (the length of the robot arms). For a detailed description of this example see (Buchberger 1987).

Example: Again, a call to a Gröbner basis package (which is meanwhile availabe in most symbolic computation software systems) with a parameter presentation [x - r t, y - r t∧2, z - r∧2] of a surface in 3D space as input, will automatically produce the implicit presentation x∧4 - y∧2 z of the same surface, see (Buchberger 1987).

Computer Analysis Symbolic computation software systems provide

• limites of symbolic expressions,

• calculations with finite and infinite power series,

• derivatives of symbolic expressions,

• indefinite and definite integral of symbolic expression,

• decision about existence of integrals in certain domains,

• Laplace transforms etc.

• symbolic solution of certain classes of differential equations,

• symbolic simplification of sums and products,

Example: The command powerseries( log(sin(x)/x), x, 0) in MACSYMA

will produce the infinite symbolic sum presentation of the input function:

                  −(∑_{i=0}^{∞} \frac{2^{2i}bern(2i)}{(2i)!})log(x) − log(x)

Example: The commands eq1:  3 * 'diff(f(x),x,2) - 2 * 'diff(g(x),x) =
sin(x); and eq2:  a * 'diff(g(x),x,2) + 'diff(f(x),x) = a * cos(x); in MAC-

SYMA define two ordinary second order differential equations eq1 and eq2. The com-

mands eq1:  laplace(eq1,x,s) and eq2:  laplace(eq2,x,s) then compute the

Laplace transform of eq1 and eq2. A call of linsolve will solve the linear equations in

the unknowns laplace(f(x),x,s) and laplace(g(x),x,s) and a call of ilt (inverse

Laplace transform) will finally give the symbolic result

       f(x) = \frac{^{\frac{27a5/2sin( \frac{\sqrt{6}x}{3\sqrt{a}} )}{\sqrt{6}(3a−2)}} − 3a^{2}cos(\frac{\sqrt{6}x}{3\sqrt{a}})}{3a} − \frac{3asin(x)}{3a − 2} + a + f(0)

        g(x) = \frac{^{\frac{9a3/2sin( \frac{\sqrt{6}x}{3\sqrt{a}} )}{\sqrt{6}}} + ^{\frac{27a2cos( \frac{\sqrt{6}x}{3\sqrt{a}} )}{6a−4}}}{3a} − \frac{(3a + 1)cos(x)}{3a − 2} + 1/2.

See (Fateman 81) for more details on this example.

Linear Algebra, Tensor Calculus Symbolic computation software systems provide • operations on matrices with symbolic entries,

• inversion, linear systems, nullspace, eigenvalues, ...

• operations on tensors.

Numerical Mathematics, Statistics Symbolic computation software systems provide routines

• for numerical computation (curve fitting, Fourier transform, Newton root finding, numerical integration, Runge Kutta DE solution, ....), and

• for statistics.

Automated Theorem Proving Symbolic computation software systems provide

• automated proofs of geometrical theorems,

• automated proofs of arbitrary first-order-formulae on the reals,

• proofs of first order equations w.r.t. equational axiom systems,

• general first order theorem proving.

Example: Apollonios’ Circle Theorem: “The altitude pedal of the hypotenuse of a right-angled triangle and the midpoints of the three sides of the triangle lie on a circle.” After introducing coordinates, a possible algebraic formulation of this problem is as follows:

for all coordinates a_{1}, …, a_{10} ∈ R:

if h_{1}(a_{1}, …, a_{10}) = 0, …, h_{8}(a_{1}, …, a_{10}) = 0, then c(a_{1}, …, a_{10}) = 0,

where the h_{i} are the polynomials describing the hypotheses of the theorem and c is the polynomial describing the conclusion of the theorem. The algebraic formulation is what is called the radical membership problem “c ∈ Radical({h_{1}, …, h_{m}})?”. Arbitrary such questions can be decided by deciding “1 ∈ Gröbner-Basis({h_{1}, …, h_{m}, z.c − 1})?”, where z must be a new indeterminate. More details on this example are contained in (Buchberger 1987). In the system (Kutzler 1988) and similar systems, proofs of the above kind can be carried out in a few seconds.

Algebraic Geometry: Symbolic computation software systems provide

• analysis of and computation in residue class rings modulo polynomial ideals (by Gröbner bases), • free resolution of polynomial ideals (determination of the sequence of syzygy

modules by Gröbner bases),

• analysis of and computation in commutative and non-commuative associative algebras (Lie, Weyl algebras), group algebras etc.

• analysis of and computation in groups given in various representations. Example: In the CAYLEY system the following sequence of interactive commands:

g:  free(a,b);
g.relations : a ↑ 8, b ↑ 7, (a ∗ b) ↑ 2, (a ↑ −1 ∗ b) ↑ 3;

h =< a ↑ 2, a ↑ −1 ∗ b >;

i = todd coxeter(g, h);
Print i;

effects the enumeration of all 448 cosets of the subgroup < a^{2}, a^{−1}b > of < a, b | a^{8}, b^{7}, (ab)^{2}, (a^{−1}b)^{3} > by the famous Todd-Coxeter algorithm.

Group Theory Zoomed: Any of the above areas could be “zoomed” revealing a wealth of problems and

solution techniques available in present symbolic computation systems. For example, in computational group theory the following can be computed:

• test for nilpotency, commutativity, solvability etc.

• coset enumeration

• normalizers

• centralizers

• central chains

• series

• lattice of (normal) subgroups

• classes of conjugacy subgroups

• orbits

• test of imprimitivity

• test of isomorphism

• word problems

• automorphism groups.

Different representations of the group theoretical objects lead to different solution algorithms for the above problems with drastically different efficiency. Therefore the study of representations and the conversion between different representations is an important subarea of computational group theory. The main representation methods are:

• generators and relations

• permutations, block permutations

• power commutators

• bases

• strong generating sets

• matrices over Z, Galois fields and algebraic number fields,

• Cayley graphs

• character tables. “Icons” of Other Symbolic Computation Areas Other important and evolving subareas of Symbolic Computation can only be men-

tioned as “icons” here:

• Symbolic Computation based computational geometry

• automatic programming

• computational number theory

• computational topology

• ... Interfaces: Symbolic computation software systems provide

• advanced 2D and 3D graphics and animation,

• interface to textprocessing,

• output in FORTRAN, C etc. syntax (symbolic computation as preprocessing!) Programming facilities: Symbolic computation software systems provide

• functional and procedural programming, • “generic” programming,

• “rewrite rules” style programming using pattern matching,

Example: Mathematica, for example, provides a convenient style of programming in the form of “rewrite rules” that is particularly convenient for mathematicians who are used present mathematical knowledge in the form of problem reduction rules (“theorems”). For example, an “algorithm” for limes computations could be quickly assembled by formulating Mathematica rules of the following style: Limes[ a + b ] := Limes[ a] + Limes[ b]. For a given symbolic input expression, Mathematica would check in its rule base whether an expression matching the pattern a + b occurs as a subexpression and would effect the corresponding transformation.

3 Examples of Recent Theoretical Results

In this section we give some samples of recent theoretical research results in the area of symbolic computation. These results are taken from papers that appeared or will appear in one of the special issues of the Journal of Symbolic Computation. A complete list of all special issues of this journal that appeared in the last five years and will appear in the next two years is contained in Section 4.8.

These samples of theoretical results should give a flavor of the breadth of ongoing foundational research in symbolic computation and should also demonstrate the depth of mathematics necessary to come up with algorithmic solutions to symbolic computation problems. Each of these results also gives rise to many important and challenging open problems that could attract the attention of mathematicians who are interested in embarking on new directions off the beaten track.

3.1 Proofs of Combinatorial Identies

In (Zeilberger, Takayama 1992) a new approach to the automated proof of combinatorial identities and the determination of definite integrals and sums is developed. It is based on the notion of “holonomic functions”. Roughly, a holonomic function is a function f for which an ideal A in the Weyl algebra of differential operators exists such that Af = 0 (and A satisfies some other properties). The class of holonomic functions is huge and includes most of the practically interesting functions like polynomials, rational functions, algebraic functions, trigonometric functions, exponential and logarithm, hypergeometric functions, binomial coefficients, Bessel functions, Legendre functions etc.

It is shown how, for an A for f(x, t) an annihilating B for g = ∫_{−∞}^{∞} f(x, t)dt can be constructed. Hence, the integral g can be obtained as a solution to the equation Bg = 0.

An essential subalgorithm in the construction of B for the elimination of variables and other purposes is a generalized version of the Gröbner bases algorithm (Buchberger 1985).

3.2 Automatic Discovery of Geometric Theorems

In (Sturmfels, Whiteley 1991) “Cayley factorization” of expressions in the Cayley algebra is discussed. The mathematical problem consists in devicing an algorithm that takes arbitrary expressions in the bracket algebra, for example, an expression of the form

− [abc][ade][bdf][cef] + [abd][ace][bcf][def]  (1)

and to generate an equivalent expression in the Cayley algebra, for example, the expression

(ab ∧ de) ∨ (bc ∧ ef) ∨ (cd ∧ fa).  (2)

The problem is open for the general case. A solution is given in the above paper for the multlinear case.

This solution, however, suffices to “automatically generate” a lot of non-trivial geometrical theorems or to automatically prove geometrical conjectures. For example, the question of finding a necessary and sufficient condition for 6 points a, b, c, d, e, f in the plane to lie on a quadric, which is equivalent to the statement that

det ( \begin{matrix}a_{1}^{2} & a_{2}^{2} & a_{3}^{2} & a_{1}a_{2} & a_{1}a_{3} & a_{2}a_{3} \\ ⋮ & & & & & ⋮ \\ f_{1}^{2} & f_{2}^{2} & f_{3}^{2} & f_{1}f_{2} & f_{1}f_{3} & f_{2}f_{3} \end{matrix} ) = 0  (3)

can be answered by transforming (by the well known “straightening algorithm”) condition ( 3) into the equivalent condition that ( 1) is zero and then, by the new Cayley factorization algorithm, into the equivalent condition that ( 2) is zero. The latter condition, however, has the immediate geometrical interpretation that the 6 points lie on a quadric if and only if certain intersection points of connection lines between the lines lie on one common straight line (Pascal‘s Theorem). This means that the theorem was automatically produced.

3.3 Point Location Problems Solved With Cylindrical Algebraic Decomposition

In (Chazelle, Sharir 1990) it is shown how a very general class of point location problems can be solved by using Collins’ well known algorithm for producing “cylindrical algebraic decompositions” of the n-space.

Given n polynomials in m variables, the m-space is naturally partitioned into a finite set of “cells”. Given a point in m-space the point location problem consists in locating the “cell” in which the point lies. (Collins 1975) showed how the decomposition of the m-space can effectively be computed by algebraic algorithms. In (Chazelle, Sharir 1990) it is shown how Collins’ decomposition can be used to solve the general point location problem in O(log n) time after O(n^{2^{d}}) preprocessing operations for building up a suitable data structure.

3.4 Black Box Algorithms

In (Kaltofen, Trager 1990) a new type of algorithms is introduced: “black box algorithms” for problems having polynomials as input and output. Their method starts from the observation that for a polynomial to be “known” it suffices to have a method that produces, for any argument, the corresponding value of the polynomial. It is not actually necessary that we know the coefficients of the polynomial.

Let us consider, for example, the factorization problem for multivariate polynomials over the integers. Given a polynomial f (i.e. given some method to compute f(a_{1}, …, a_{n}) for arbitrary arguments), the factorization problem is solved if we know a method that, given any (x_{1}, …, x_{n}), produces the values h_{1}(x_{1}, …, x_{n}), …, h_{m}(x_{1}, …, x_{n}) of the factors h_{1}, …, h_{m} of f. This method may use calls of f for various (a_{1}, …, a_{m}) as “oracles”. In the paper, such a method is developed for the factorization problem and related problems and it is shown that polynomial time complexity can be achieved.

3.5 Polycyclic Quotient Algorithm

In (Sims 1990) an important problem of computational group theory is treated: the computation of polycylcic quotient groups for a group given by a finite presentation. The paper starts from an earlier method by Baumslag-Cannonito-Miller that did not fully cover all the algorithmic subproblems. (Sims 1990) fills the gaps by giving a method how to completely reveal the structure of two residue class rings that appear in the construction. This new method is a modification of the Gröbner basis technique.

3.6 Linear Diophantine Equations and Unification

The problem of unification can be considered to be the most general formulation of the problem of solving equations in arbitrary first order theories. It is well known that the unification problem in “AC”-theories (theories involving only equational axioms for associative-commutative function symbols) can be reduced to the problem of solving systems of linear diophantine equations over the natural numbers.

Earlier solutions of the linear diophantine equations problems relied on systematic enumeration. In (Clausen, Fortenbacher 1989) a new method is presented that uses certain “completion” steps that can be interpreted as “walks” in certain labeled digraphs. Significant speed-up can be achieved by this new approach.

3.7 Gröbner Fans of Ideals

The method of Gröbner bases has numerous applications in polynomial ideal theory and related areas (algebraic geometry, geometric modeling). Gröbner bases depend on an underlying “admissible” ordering of power products. There are infinitely many “admissible” orderings. In (Mora, Robbiano 1988) it is shown that, for a given polynomial ideal, the infinitely many admissible orderings fall into finitely many classes. One class corresponds to exactly one Gröbner basis. Furthermore, it is possible to compute, for a given polynomial ideal, one “universal” Gröbner basis, i.e. a set of polynomials that is a Gröbner basis for the given ideal under all possible admissible orderings.

3.8 Cluster-Based Cylindrical Algebraic Decomposition

As explained above, Collins’ algorithm constructs, for n polynomials in m variables, a decomposition of the n-space into “sign-invariant cells”. The computation proceeds by, first, reducing the problem for the n-space to the problem for the (n − 1)-space and then showing how to construct a solution for the n-space from a solution for the (n − 1)-space. The latter construction proceeds by building a “stack” of n-cells over each (n − 1)-cell.

In (Arnon 1988) it is shown how the cells of the (n − 1)-space can be automatically clustered into bigger sign-invariant blocks. In Collins’ algorithm it then suffices to erect stacks over these bigger, and fewer, blocks. By recursion, this may save enormous time in the construction of the n-space decomposition.

4 A Guide to the Literature and Software Systems

4.1 References to Papers Cited in the Text

(Arney et al. 1990) David C. Arney, Jeffrey Misner, Derive as a Research Tool, this conference.

(Arnon 1988) D.S. Arnon, A Cluster-Based Cylindrical Algebraic Decomposition Algorithm, Journal of Symbolic Computation 5/1-2, February/April 1988.

(Buchberger 1985) Bruno Buchberger, Gröbner Bases: An Algorithmic Method in Polynomial Ideal Theory, Chapter 6, pp. 184-232 in: N.K. Bose: Multidimensional Systems Theory, D. Reidel Publishing Company.

(Buchberger 1987) Bruno Buchberger, Proceedings Workshop on Scientific Software, IMA, Minneapolis, USA, March 23-26, 1987, pp.59-88, IMA Volums in Mathematics and its Applications, Volume 14, Springer.

(Chazelle, Sharir 1990) B. Chazelle, M.Sharir, An Algorithm for Generalized Point Location and its Applications, Journal of Symbolic Computation 10/3-4, September 1990.

(Clausen, Fortenbacher 1989) M. Clausen, A. Fortenbacher, Efficient Solutions of Linear Diophantine Equations, Journal of Symbolic Computation 8/1-2, July/August 1989.

(Collins 1975) G.E. Collins, Quantifier Elimination for Real Closed Fields by Cylindric Algebraic Decomposition, Proceedings 2nd GI Conference on Automata Theory and Formal Languages, Springer Verlag, LNCS 33, Berlin, 1975, pp. 515-532.

(Fateman 1981) Richard J. Fateman, Symbolic and Algebraic Computer Programming Systems, ACM SIGSAM Bulletin, Volume 15, Number 1, 2/81, pp.21-32.

(Kaltofen, Trager 1990) E. Kaltofen, B. Trager, Computing with Polynomials Given by Black Boxes for their Evaluations: Greatest Common Divisors, Factorization, Seperation of Numerators and Denominators, Journal of Symbolic Computation 9/3, March 1990.

(Kutzler 1989) Bernhard Kutzler Algebraic Approaches to Automated Geometry Theorem Proving, PhD Thesis, RISC-Institute, University of Linz, Austria, November 1988.

(Mora, Robbiano 1988) T. Mora, L. Robbiano, The Gröbner Fan of an Ideal, Journal of Symbolic Computation 6/2-3, October/December 1988.

(Sims 1990) C. Sims, Implementing the Baumschlag-Cannonito-Miller Polycyclic Quotient Algorithm, Journal of Symbolic Computation 9/5-6, May/June 1990.

(Sturmfels, Whiteley 1991) B. Sturmfels, W. Whiteley, On the Synthetic Factorization of Projectively Invariant Polynomials, Journal of Symbolic Computation 12/4-5, October 1991.

(Wang 1990) Paul S. Wang, Advances in integrating Symbolic, Numeric and Graphics Computing, this conference.

(Zeilberger, Takayama 1992) D. Zeilberger, N. Takayama Computerized Proofs of Combinatorial and Special Function Identities, Journal of Symbolic Computation 13/5-6, June 1992.

4.2 Symbolic Computation Software Systems

Some of the more important symbolic computation software systems are listed here in alphabetic order with some characterizing information in the order

• developed since which year

• address for ordering the system

• available on which machines

• some characteristic features.

CAYLEY V4

• since the early 1970’s, steadily expanded and improved

• Prof. John Cannon Department of Pure Mathematics University of Sidney Sidney NSW 2006

• Workstations of Apollo, DEC, IBM, SUN.

IBM machines running VM/CMS and VAX machines running VMS.

• Cayley V4 is a system designed for solving problems in algebra, number theory and algebraic combinatorics, with strong emphasis on structural questions. A user language based on the concepts of set, mapping and algebraic structure provides a natural notation for algorithms in this area.

DERIVE

• 1990 (Version 1.62)

• Soft Warehouse, Inc.

3615 Harding Avenue, Suite 505

Honolulu, HI 96816

Phone: (808) 734-5801

• IBM PC compatible machines under MS-DOS: approximately 200 $.

• The computer algebra system Derive is designed for use on microcomputers. A very compact system. A menu-driven interface makes Derive easy and natural to use. Derive has great potential as a teaching aid.

MACSYMA

• 1988 (Version 412.6)

• Computer Aided Mathematics Group Symbolics Inc. New England Executive Park East Burlington, MA 01803 Phone: (617) 221-1250 Fax: (617) 221-1099

• 386-based MS-DOS systems.

Workstations of Apollo, DEC, Symbolics, SUN.

• Macsyma is a general system for numerical, symbolic and graphical computation. It offers over 1300 documented commands for solving a wide range of mathematical problems.

MAPLE

• 1989 (Version 4.3)

• Waterloo Maple Software 160 Columbia Street West Waterloo, Ontario, Canada N2L 3L3 Phone: (519) 747-2373 Fax: (519) 747-5284

• 386-based: approximately 680 $. Atari ST, Apple MacII, MacSE, MacPlus: approximately 380.00 $. Workstations of Apollo, DEC, HP, IBM, MIPS, Silicon Graphics, SUN and many others: approximately 2400 $.

• Maple is a powerful and user-friendly system for numerical, symbolic and graphical computation that incorporates a high-level programming language. It delivers a large library of about 2000 mathematical functions. Maple requires remarkably little memory and is therefore an ideal multi-user system.

MATHEMATICA

• 1989 (Version 1.2)

• Wolfram Research, Inc.

P.O. Box 6059 Champaign, Illinois 61821 Phone: 217-398-0700 Fax: 217-398-0747

• 386-based MS-DOS systems: approx. 695 $.

Apple MacII, MacSE, MacPlus: approx.495 $. Workstations of Apollo, DEC, HP, IBM, MIPS, Silicon Graphics, SUN and many others: approx. 2,250 $.

• Mathematica is a general system for numerical, symbolic and graphical computation. The system produces excellent 2D and 3D PostScript graphics and incorporates a modern high-level programming language with pattern-match and rewriting style programming. On the Macintosh, Mathematica has a sophisticated user interface which supports interactive textbooks.

REDUCE

• 1988 (Version 3.3)

• Dr. A.C. Hearn The RAND Corporation P.O. Box 2138 Santa Monica, CA 90406-2138

• Reduce has been implemented on many different computers ranging in power from the IBM PC to the Cray X-MP.

• Reduce is a general-purpose computer algebra system designed for physicists, mathematicians and engineers. Since, at present, Reduce is the most widely-used computer algebra system in a number of countries many application packages are available. Users with access to any of the major research computer networks can obtain newly released packages and other material from a digital library.

SAC-2

• Since the early 1970’2, continuously expanding and improving.

• Prof. George Collins Computer Science Department Ohio State University Columbus, Ohio

• Available on all machines having a FORTRAN or C compiler.

• SAC-2 is a collection of carefully designed algebraic algorithms mainly for algorithms on polynomials including Collins’ decision algorithm for the logical theory of real closed fields. The algorithms are the basis for many implementations in other systems. ALDES, the programming language of the system, is compiled into FORTRAN or C and, thus, makes the system widely available and fast. All algorithms are availabe in source code and are scientifically documented.

SCRATCHPAD

• Prototyp

• Richard D. Jenks Computer Algebra Group IBM Research Division T.J. Watson Research Center P.O. Box 218 Yorktown Heights, NY 10598

• IBM mainframes under VM/CMS.

RT/PC and PS/2 under AIX.

• Scratchpad is a general computer tool for mathematics. Its design is based upon abstract datatypes which are organised into programmable algebraic hierarchies. Scratchpad’s modular library has over 200 datatypes. In addition, there is a growing library of algebraic functions. Scratchpad has an interactive language for easy access to library facilities and simple programming tasks.

4.3 Text Books and Survey Books on Computer Algebra

Akritas, A.G. (1989). Elements of Computer Algebra with Applications. John Wiley and Sons.

Buchberger, B. (ed.) (1985). Computer Algebra. Proceedings of EUROCAL 85, Vol. 1 (Invited Lectures). Springer LNCS 203. (A collection of survey lectures on some main topics in computer algebra.)

Buchberger, B., Collins, G.E., Loos, R. (Eds.) (1982). Computer Algebra: Symbolic and Algebraic Computation. Springer Verlag, Wien - New York. (This is not really a text book but a collection of survey articles on the main subareas of computer algebra. Some of the articles, in addition, contain details of theorems and algorithms not available in other text books.)

Davenport, J.H., Siret, Y., Tournier, E. (1988). Computer Algebra: Systems and Algorithms for Algebraic Computation. Academic Press, London. (The first real text book on computer algebra. For some of the subjects treated, no proof details are given. Instead, references to the original literature are provided.)

Della Dora, J., Fitch, J. (1989). Computer Algebra and Parallelism. Academic Press.

Knuth, D.E. (1981). The Art of Computer Programming. Vol. 2: Seminumerical Algorithms. Addison-Wesley, Reading. (The algorithms, together with their mathematical foundation, for arithmetic in the most important algebraic domains are given in this book.)

Janßen, R. (1988). Trends in Computer Algebra.. Springer.

(A collection of survey lectures at an international sympolsium in Bad Neuenahr, May 1987.)

Lipson, J.D. (1981). Elements of Algebra and Algebraic Computing. (This text book is a systematic introduction to basic areas of algebra together with algorithms for the algebraic problems discussed. However, it covers only a part of what today is computer algebra.)

Mignotte, M. (1989). Mathematiques pour le calcul formel. Presses Universitaires de France.

4.4 Survey Articles on Computer Algebra:

Buchberger, B., Kutzler, B. (1986). Computer-Algebra für den Ingenieur. In: Rechner-Orientierte Verfahren (Buchberger et al. eds.). Teubner, Stuttgart, pp.11-64.

Caviness, B.F. (1985). Computer Algebra: Past and Future. J of Symbolic Computation 2/3, 217-236.

Kaltofen, E. (1987 ). Computer Algebra Algorithms. In: Annual Review of Computer Science Vol.2, 91-118 (J.F. Traub ed.), Annual Review Inc., Palo Alto, California.

Yun, D.Y.Y., Stoutemyer, R.D. (1980). Symbolic Mathematical Computation. In: Encyclopedia of Computer Science and Technology ( J. Belzer et al. eds.), Vol. 15, 235-310, M. Dekker, New York - Basel.

4.5 Books on Subareas of Computer Algebra:

Davenport, J.H. (1981). On the Integration of Algebraic Functions. Springer LNCS 102. (Published version of a Ph.D. thesis.)

Atkinson, M.D. (ed.) (1984). Computational Group Theory. Academic Press, London. (Proceedings of the 1983 LMS Symposium in Durham. There is no text book on computational group theory. These proceedings may serve as a possible starting point for obtaining an overview on the subject.)

Stauffer, D., Hehl, F.W., Winkelmann, V., Zabolitzky, J.G. (1988). Computer Simulation and Computer Algebra. Springer.

Tournier, E. (1989). Computer Algebra and Differential Equations. Academic Press.

4.6 Books on Applications of Computer Algebra:

Caviness, B.F., Gilbert, R.P., Shtokhamer, R. (19??). An Introduction to Applied Symbolic Computation Using MACSYMA. (In preparation).

Howard, J.C. (1979). Practical Applications of Symbolic Computation. IPC Science and Technology Press, Guildford, England. (Some application examples, using FORMAC, are given in much detail. Somewhat out of date.)

Klimov, D.M., Rudenko, V.M. (1989). Computer Algebra Methods for Mechanics Problems. Moskva.

Pavelle, R. (Ed.) (1985). Applications of Computer Algebra. Kluwer Academic Publisher, Boston - Dordrecht - Lancaster. (A collection of application papers using MACSYMA).

Rand, R.H. (1984). Computer Algebra in Applied Mathematics: An Introduction to MACSYMA. Pitman Publishing Inc., Marshfield MA. (Examples of using MACSYMA. Not so much a primer of MACSYMA.)

Rand, R.H., Armbruster, D. (1987). Perturbation Methods, Bifurcation Theory and Computer Algebra. Springer. (Application of computer algebra in a special area.)

4.7 Books on Specific Computer Algebra Systems:

Rayna, G. (1987). REDUCE: Software for Algebraic Computation. Springer, New York. (Introduction to REDUCE with case studies.)

Symbolics Inc. (1987). MACSYMA User’s Guide. (A primer for getting acquainted with MACSYMA.)

Wooff, C., Hodgkinson, D. (1987). muMATH: A Microcomputer Algebra System. Academic Press, London. (A tutorial on muMATH.)

4.8 Journals on Computer Algebra:

[JSC] Journal of Symbolic Computation (B. Buchberger et al. eds.). Academic Press London, 1985- . (The first refereed journal on computer algebra and all other areas of symbolic computation. In addition to the regular issues it frequently publishes special issues on certain subareas of computer algebra. For example, • Vol. 3/1-2 (Feb 1987). Rewriting Techniques and Applications. (J.P. Jouannoud

ed.)

• Vol. 4/1 (August 1987). Algorithmic Methods in Algebra and Number Theory. (M. Pohst ed.)

• Vol. 5/1-2 (April 1988). Algorithms in Real Algebraic Geometry. (D. Arnon and B. Buchberger eds.)

• Vol. 6/2-3 (Oct 1988). Computational Aspects of Commutative Algebra. (L. Robbiano ed.)

• Vol. 7/3-4 (March - April 1989). Unification: Part 1. (C. Kirchner ed.)

• Vol. 8/1-2 (July - Aug. 1989). Unification: Part 2. (C. Kirchner ed.)

• Vol. 9/3 (March 1990). Complexity of Algebraic Algorithms. (E. Kaltofen ed.)

• Vol. 9/5-6 (May - June 1990). Computational Group Theory. (J. Cannon ed.)

• Vol. 10/3-4 (Sept. - Oct. 1990). Computational Geometry. (E. Welzl and R. Seidel eds.)

• Vol. 11/1-2 (Jan. - Feb. 1991). Rewriting Techniques for Theorem Proving. (J. Hsiang and L. Bachmair eds.)

• Vol. 12/4-5 (Oct. - Nov. 1991). Invariant Theoretic Algorithms in Geometry. (B. Sturmfels and N. White eds.)

• Vol. ? (June - July 1992). Symbolic Algorithms for Combinatoric Identities. (P. Paule and D. Zeilberger eds.))

Journal of Applicable Algebra and Error Correcting Codes. Springer, New York-Heidelberg, 1990- . (A recent journal emphasizing the application of Computer Algebra to coding theory and related subjects.)

Journal of Automated Reasoning. Reidel Publishing Company, 1985- . (This journal specializes in Symbolic Comutation algorithms in the area of automated theorem proving.)

ACM SIGSAM Bulletin. Distributed by the ACM Special Interest Group on Symbolic and Algebraic Manipulation. (This is a non-refereed informal bulletin for the fast dissemination of papers, implementation notes, announcements, bibliographies etc. in the area of computer algebra.)

Acknowledgement: This paper was written in the frame of the project “Gröbner Bases” sponsored by the “Österreichisches Ministerium für Wissenschaft und Forschung”. I am grateful to my student W. Windsteiger who helped in the production of the manuscript.