sci.math.symbolic

Long-form reference · 1,878 words · about an 8-minute read

The group and its era

Computer algebra was an established research field before Usenet carried it. The first systems appeared in the 1960s out of two quite different pressures — theoretical physicists facing enormous expressions, and artificial-intelligence research into symbolic manipulation — producing Schoonschip, written by Martinus Veltman in 1963, then MATHLAB, REDUCE and Macsyma, whose descendants were still argued over here three decades later.

The chronology is worth setting out, because the group’s habit of comparing systems only makes sense against it. FORMAC was built at IBM by Jean E. Sammet and her team from 1962, as an extension of FORTRAN IV, and released to customers in November 1964; Carl Engelman wrote MATHLAB at MITRE in 1964, in Lisp. Anthony C. Hearn began REDUCE in 1963 out of high-energy physics, writing it in a Lisp dialect of its own; it is one of the oldest of these systems still in active use. Macsyma was developed from 1968 to 1982 at MIT’s Project MAC, begun in July 1968 by Engelman, William A. Martin and Joel Moses. IBM’s second Scratchpad, the one that became Axiom, was developed from 1977 at the Thomas J. Watson Research Center under Richard Dimick Jenks.

What distinguished sci.math.symbolic from the rooms attached to particular products was that no vendor owned it. Maple, Mathematica, REDUCE, Macsyma, Derive, MuPAD and Axiom were all in scope, and the useful posts were the ones that crossed between them. Their foundations genuinely differed: Axiom, descended from IBM Research’s Scratchpad II, rested on a strongly typed hierarchy in which rings and fields are themselves objects; MuPAD came out of the University of Paderborn, passed to SciFace Software in 1997, and ended up inside MATLAB’s Symbolic Math Toolbox after MathWorks bought SciFace in September 2008.

The commercial generation of the 1980s set the terms the group inherited. Maple grew out of a meeting at the University of Waterloo in late 1980, Waterloo Maple Inc. being founded in 1988 to sell it; Mathematica 1.0 was released on 23 June 1988 by Wolfram Research; and Soft Warehouse of Honolulu, which had produced muMATH, released Derive in 1988 for MS-DOS. Macsyma itself left the university in the same period: licensed to Symbolics in 1982, bought from the ailing Symbolics by Macsyma, Inc. in 1992, and acquired by Tenedos LLC in 1999. By the time the newsgroup was busy, most of the systems under discussion had changed hands at least once.

The readership matched the remit: people who taught with these systems, who published results computed with them, and in some cases who had worked on them. A claim about what a system did could be answered by someone who knew why.

Beside the general-purpose systems ran packages built for one branch of algebra, and they surfaced here whenever a general system proved too slow for a particular computation. GAP — groups, algorithms and programming — began in 1986 at RWTH Aachen and its coordination later moved to the University of St Andrews. PARI/GP was started in 1985 by a team led by Henri Cohen at Bordeaux, for number theory. Macaulay, for commutative algebra and algebraic geometry, was begun in 1983 by Dave Bayer and Michael Stillman, with Macaulay2 following from 1993 with Daniel Grayson; Singular, at Kaiserslautern, took polynomial computation with an emphasis on singularity theory.

What was discussed

The field’s own algorithms were the technical backbone. Symbolic integration has a decision procedure — the Risch algorithm, developed by Robert Risch in 1968 — which decides whether an elementary function has an elementary antiderivative and, if so, produces it; applied to general elementary functions it is strictly a semi-algorithm, since it must determine whether certain expressions are zero, and no complete implementation exists even now. Gröbner bases, introduced by Bruno Buchberger in his 1965 thesis and named for his supervisor, gave polynomial systems and ideal membership an algorithmic treatment, at the cost of intermediate polynomials that can exhaust a machine before a small final answer appears. Factorisation over various domains was a third staple.

A further decision procedure of the same family was cylindrical algebraic decomposition, introduced by George E. Collins in 1975 together with an algorithm for computing it: an effective quantifier elimination over the real numbers, cheap enough to be implemented where the construction behind the Tarski–Seidenberg theorem was not. Procedures of this kind are why a computer algebra system is more than a large table of rewriting rules, and they also explain its disappointments: each is exact but expensive, so implementations reach for heuristics first and fall back on the decision procedure only when they must. That gap between the published algorithm and the shipped command is where a great deal of this group’s traffic lived.

Behind all of it sat the question the field could not dispose of: what simplify should mean. Richardson’s theorem, proved by Daniel Richardson in 1968, shows equality to be undecidable for a modest class of expressions built from integers, π, ln 2, exponentials and sines; no simplifier can therefore be complete over that class, and every system’s simplification command is a body of heuristics with a boundary somewhere. Joel Moses had set the design problem out in 1971, under the title Algebraic Simplification: A Guide for the Perplexed.

This is why a bug list points a reader here. A system that returns a wrong closed form fails differently from one that loses precision: the output looks exact, carries no error bar, and may be right on a branch the user is not standing on. Much of what arrives as a bug report is not one — branch cuts, unstated assumptions about a parameter’s sign or domain, correct answers in an unrecognised form. Telling those from real defects wants a second opinion, and the standard method was comparison: the same input put to several systems. Michael Wester’s survey of 1999 systematised the comparison, running the same short problems across Axiom, Derive, Macsyma, Maple, Mathematica, MuPAD and REDUCE; the resulting test suite was reused as a benchmark.

Individual test cases outlived the discussion that produced them. An algebraic integrand offered to this group by Henri Cohen in 1993 — x/sqrt(x^4+10*x^2-96*x-71), which has an elementary antiderivative where the same expression with 71 changed to 72 does not — is still cited in reference accounts of the Risch algorithm.

The reason a correctness argument wants a room like this one rather than a vendor’s is structural. A defect reported inside a vendor’s own forum reaches the people who can repair it, which is where a defect belongs. But the same integrand put to four systems produces something a single-product forum has no occasion to publish: a table in which the systems disagree — one returning a closed form, another leaving the integral unevaluated, another an answer correct on a branch the asker was not standing on. That table decides whether the fault lies in an implementation or in the question, and only an unaffiliated group has reason to publish it.

A field with its own institutions

Computer algebra had a peer-reviewed home before it had a newsgroup, which is why a thread here could end in a citation rather than in an opinion. The professional body is SIGSAM, the Association for Computing Machinery’s Special Interest Group on Symbolic and Algebraic Manipulation, which publishes the ACM Communications in Computer Algebra.

Its conference is ISSAC, the International Symposium on Symbolic and Algebraic Computation, whose first meeting was held in Rome from 4 to 8 July 1988; it is regularly sponsored by SIGSAM, and its proceedings have been published by the ACM since 1989. It succeeded a run of meetings held between 1966 and 1987 under the names SYMSAM, SYMSAC, EUROCAL, EUROSAM and EUROCAM — two decades of them, before Usenet gave the discipline an open door.

The journal literature arrived in 1985, when Bruno Buchberger started the Journal of Symbolic Computation, published by Elsevier and covering computer algebra, computational geometry and automated theorem proving; he went on to found the Research Institute for Symbolic Computation at Johannes Kepler University in 1987. For a reader tracing a disputed result this apparatus matters: an algorithm argued over in a thread almost always had a published description somewhere inside it, and part of what the group did was point people at it.

The free-software succession

The systems compared here did not all stay proprietary, and the licence changes of the following decade moved the conversation as much as any technical development did. The Macsyma line reached free software first: Bill Schelter maintained a version from 1982 until his death in 2001, and in 1998 he obtained permission from the United States Department of Energy to release it under the GPL; that version is Maxima. Because it descends from the 1982 code it does not carry the modifications made to the commercial branch afterwards, so the two lines diverged and could hold different defects — the sort of distinction this group was equipped to notice.

The others followed at their own pace. Axiom was withdrawn from the market in 2001 and re-released under the Modified BSD License; REDUCE, previously sold for $695, was open-sourced in December 2008 under a modified BSD licence; and among the specialist packages GAP, PARI/GP, Singular and Macaulay2 were all distributed under the GNU General Public License. The effect on a correctness argument was large: a claimed defect could now be traced into source by the person reporting it, and the cross-system comparison the group had run by hand became something a reader could reproduce without buying four licences.

Context

The sci.* mathematics groups divided their traffic by kind rather than by subject. sci.math took everything at every level; sci.math.research was moderated, so that research-level discussion could proceed clear of the open group’s noise; sci.math.num-analysis held the numerical side. sci.math.symbolic sat between them, narrower than the parent and less formal than the moderated group.

Alongside these ran the vendor-adjacent groups under comp.soft-sys.math, among them comp.soft-sys.math.maple, documented at length elsewhere on this site, with a moderated Mathematica group beside it. The division was of subject matter, not standing: product questions there, algorithms and cross-system comparison here. The boundary leaked both ways.

The dispersal followed the pattern of technical Usenet generally. Vendor forums and mailing lists took the product questions; Stack Exchange later took much of the rest. The open-source lineages grew channels of their own — Maxima, descended from Macsyma; SageMath, released in February 2005 by William Stein at the University of Washington, wrapping existing packages behind a Python interface; SymPy, begun in 2005 by Ondřej Čertík — where a disputed result becomes a filed issue with a reproducible input, close to what this group did without the infrastructure.

What the archive preserves is the comparative record: one input, several systems, in public.