Computer algebra package

From Encyclopedia of Mathematics
Jump to: navigation, search

computer algebra system

A computer program focusing on exact mathematical formula manipulation. It differs from numerical packages in that it manipulates symbols rather than numbers; thus, it does calculations in exact mode. For instance, integers are regarded as strings of digits of arbitrary length and $\sqrt 3$ is regarded as an algebraic symbol with the property that it squares to $3$. The early computer algebra packages rose out of the need for heavy computations in physics (Schoonschip by T. Veltman is an example). The earliest among the widely available systems is REDUCE, which runs on many platforms and is still being further developed.

Two more early packages were MACSYMA and SMP, both widely available by 1983. Maple was released in 1986, while Scratchpad II (later called AXIOM) and Mathematica appeared by 1988.

The success of these packages has been made possible by the growth of computer memory, which could handle better than before the enormous "intermediate expression swellintermediate expression swell" that so often takes place in exact computations. Still, there are severe limitations on the size of the mathematical computations that can be done effectively on a computer. For instance, the complexity of the very useful Buchberger algorithm keeps it from finding say, all solutions of a sufficiently generic set of $7$ equations in $7$ variables of degree $4$ over the rational numbers in a reasonable time.

Usually, a distinction is made between general-purpose packages and special-purpose packages.

General-purpose packages.

Among the objects handled by these systems are polynomials over effective rings (e.g., the integers, the rational numbers, algebraic number fields, finite rings), strings of characters, vectors, matrices, solutions of equations, explicitly described functions, series, etc. Additionally, there are commands enabling the user to perform operations on these objects. For instance, functions can be differentiated, integrated, expanded in a series around a point, simplified, brought into normal form, numerically evaluated at a given point, etc. Common features are plotting facilities, effective linear algebra, libraries with standard and special functions (e.g., trigonometric and Gamma-functions, Hermite polynomials) and (differential and polynomial) equation solving.

Most packages provide a programming language in which the built-in operations can be used with reserved names. In this language, users have written complete packages for particular fields of research; these packages constitute the so-called share library of the general-purpose system.

The most important examples of general-purpose systems are (in alphabetical order) AXIOM, Derive, Maple, Mathematica, and REDUCE. Their design features differ considerably. For instance, Mathematica is a rule-based system, whereas Maple's language is procedural, and AXIOM uses an object-oriented approach. Derive is a symbolic calculator on a PC, but does not have strong programming facilities.

Some examples of user-written packages for particular fields are, for commutative algebra: CALI (a REDUCE package), CASA (a Maple package for constructive algebraic geometry), IDEALS (a REDUCE package); for non-commutative algebra: NCALGEBRA (in Mathematica) and the Grassmann package (in Maple); for differential equations: PDEtools, StandardForm, liesymm, and diffgrob2 (in Maple), DELiA and LIE (in Mathematica), SYMMGRP.MAX and SYMDE (in MACSYMA), CRACK and ODESOLVE (in REDUCE), PDELIE (Lie symmetry group methods package in MACSYMA); for tensor calculus: MathTensor and Ricci (in Mathematica), Redten (in REDUCE), GRTensorII (in Maple and in Mathematica).

Apart from the above five commercial products, there are some freely available systems, although usually not with such huge libraries of functions. An example is MuPAD, the design of which resembles Maple's, although it also allows for parallelism.

Further examples of general-purpose packages are derivatives from MACSYMA (with names ALJABR, MACSYMA (R), MAXIMA, PARAMACS, PARAMAX, PUNIMAX, VAXIMA; all of them are written in Lisp), FORM (suitable for computing with extremely large mathematical objects), Magma and to a certain extent GAP (see below), and SENAC (a Software Environment for Numerical and Algebraic Computation).

More and more packages come with ways to link them to other software (e.g., MathLink for Mathematica, MathEdge for Maple) and allow for system calls to be made from within. There is a tendency towards advanced user interfaces (discoupled from the mathematical engine part) in which mathematics can be edited in very direct ways, with facilities to output mathematical objects in any one of the most common ways (HTML, TeX, or in the system's input format). This is supported by the OpenMath movement, which strives for a protocol for communicating mathematical data and instructions among individual packages.

Special-purpose packages.

In general, special-purpose packages differ from general-purpose systems in at least two ways. First, as the name suggests, the former deal with a special part of mathematics. Second, this is often compensated by the fact that they perform much better in their field than the general-purpose packages. Most special-purpose packages do not have powerful human interfaces.

Recently, the differences between the general-purpose and special-purpose packages have become vaguer, particularly since some of the special-purpose packages have been expanded enormously. Examples are the group-theory packages Cayley (later turned into Magma) and GAP. The latter system, for instance, has a share library with packages such as ELIAS (for Lie algebra analysis), GRAPE (for graphs), and GUAVE (for codes).

More typical examples of special-purpose packages are LiE (for data regarding Lie group representations), MeatAxe (for high-dimensional matrix groups defined over finite fields), NAUTY(for the automorphism group of a graph), and SISYPHOS (for $p$-groups and their modular group algebras). All five can also be invoked from GAP. In this manner the special-purpose packages can be seen as modules, which can be plugged into bigger packages.

For group theory, besides those mentioned above, there are ANU Software (for nilpotent and solvable quotient determination), CHEVIE (for Chevalley groups), Schur (for data regarding Lie group representations), and Symmetrica (for representation theory, invariant theory and combinatorics of the symmetric group).

For number theory, the best known special-purpose packages are PARI (mainly written in C, very speedy, but not a symbolic manipulation package in the strict sense as, e.g., $\sin x$ is immediately expanded as a Taylor series) and KANT. Version 2 of the latter has been built into Magma and is written in Ansi-C (there is a version with a shell of its own, called KASH). Furthermore, there are Galois (for teaching purposes, on PC), MALM (built in Turbo Pascal and UBASIC), and SIMATH (written in C, also usable in FORTRAN programs).

For (non-) commutative algebra and algebraic geometry, several systems are available: Albert (for non-associative algebras), Bergman (for calculating Gröbner bases from homogeneous input in terms of polynomials in the commutative or the non-commutative polynomial rings over the rationals or a finite prime field), CoCoA (small but efficient, written in C), FELIX (PC version only, for Gröbner bases of non-commutative algebras), GANITH (an algebraic geometry toolkit for the computation and visualization of algebraic equations), GB (dedicated to solving polynomial equations), GRB (for algebraic and homological manipulations on algebras and modules), KAN (for computations (e.g. Gröbner bases) in rings of polynomials, differential operators, difference operators, $q$-difference operators), Macaulay (dedicated to solving polynomial systems, syzygies, etc. over fields of prime order), and SACLIB (a library of C programs for computer algebra, supporting a package GROEBNER for Gröbner basis computations), Singular (for singularity theory and algebraic geometry; it can compute with ideals and modules generated by polynomials or polynomial vectors over polynomial or power series rings and generalizations).

For differential equations one has: DESIR (computing the basis of formal solutions of ordinary homogeneous differential equations with polynomial coefficients over the rationals), DIMSYM (for computing symmetries of distributions of vector fields or differential forms on finite dimensional manifolds), and SPDE (for determining the Lie symmetries of a given system of partial differential equations).

For tensor calculus, apart from the above mentioned share library packages, there are SHEEP (primarily for the needs of general relativity) and STENSOR (for tensor and non-commutative algebra, using symbolic indices), runnable independently and inside REDUCE.

How to Cite This Entry:
Computer algebra package. Encyclopedia of Mathematics. URL:
This article was adapted from an original article by A.M. Cohen (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article