Compact Computer Algebra

Over forty years ago an algebra system was written in Cambridge, UK, designed to assist in a number of calculations in celestial mechanics and later in relativity. We present the hardware environment and the main design decisions that led this system, later dubbed CAMAL, to be used in many applications for twenty years. Its performance is investigate, both in its own time, and more recently. It is argued that a compact data representation as in CAMAL has real benefits even in today's larger memory world.

Most of the original literature about Maple described it as a "compact and efficient computer algebra system". It was partly our goal to be able to run in small desktop computers and even on a pocket computer (the term "pocket symbolic" was also used). This talk will concentrate on four aspects of the early design that went in this direction and were the cornerstones of the design. These are the use of the language C, the S^2T measure of complexity, option remember and its implication which is the unique representation of subexpression and the systematic elimination of quadratic algorithms.

Knuth is said to have described Computer Science as "that part of mathematics in which log log n = 3". In this talk I will consider only some parts of Computer Algebra, and the even more special case when log n = 3, or even less, and where compactness of the algorithm itself, as well as the data structures, is important. g.c.d. This has been a bugbear of computer algebra for over forty years, and has given rise to many solutions, some of then truly heroic [CGG84, DP85]. Though difficult to prove, the subresultant algorithm [Col67] is quite short to program, and its intermediate expression swell does not manifest itself on small examples. It may well be worth considering the trial division variant of [Hea79].

Factoring (of univariate polynomials). This has been a challenge for almost as long as the g.c.d. problem, and is still far from being solved, as significant improvements keep on being made [vH02]. Nevertheless, if log n = 3, we can devise a relatively simple algorithm on the following lines.

1. To factor mod p, use Cantor-Zassenhaus [CZ81].
2. Possibly use several primes -- see question 1 below.
3. Having decided that there is a viable factorization, we have to lift it p-adically. Again, we note that while an optimal lifting is a very com plicated body of code, linear lifting [DST93, p. 168], with imposed leading coefficients [DST93, pp. 174-5], is not.
4. Obviously, any p-adic factor which divides over the integers is a true factor. If this doesn't happen, we have two choices.
   • Do appropriate recombinations and trial divisions. The code is not lengthy, but the running may well be, since most optimisations ([ABD85] is possibly a counterexample) will substantially lengthen the code.
   • Just give up, and declare "I couldn't find any factors, but they may nonetheless exist". In practice, this may well be acceptable on a compact system.

Factoring (of multivariate polynomials). It's not clear to this author that this is worth implementing. Integration Here the Risch-Norman [NM77] algorithm can be quite short to program, and, while not a full decision procedure, is complete on a reasonable range of transcendental integrands [Dav82]. There is a recent extension [Kau08], which looks promising on many cases of algebraic integrands. Here the aim would be to integrate correctly many common cases, while not guaranteeing that "I can't" is equivalent to "no-one can".

Open Research Questions

[Mus78] suggests that the answer is 5, though there are heuristic arguments that this should grow as log log d, where d is the degree of the polynomial to be factored. If d is small, can we get away with less?

References

[abstract in PDF]

Matrix multiplication is a cornerstone of linear algebra algorithms; its asymptotic complexity has attracted a lot of attention in the last forty years. Small dimension matrices with large entries are used to evaluate holonomic functions, by means of the binary splitting algorithm. As an example, we may consider computing exponential at 1; this computation requires matrix multiplication, on matrices of size 2. Our objective is to obtain matrix multiplication procedures that reduce the number of multiplications required for such small matrices.

We base our work on an optimized usage of the previous algorithms for small matrix multiplications, due to Strassen, Winograd, Pan, Laderman, etc.; we show how to exploit all of these standard algorithms for larger matrix multiplication in an improved way.

As a result, we were able to get lower numbers of multiplications for matrix sizes 1 to 30. We wrote a code generator that uses this table to write generate multiplication code for long integers and polynomials. Our future goal includes extending this tool for matrix multiplications having linear recurrence operators (or more generally, elements of an Ore algebra) as entries.

Online recognition of handwritten mathematical expressions can significantly improve mathematical user interfaces, especially in mobile devices, provided that it is accurate and does not cause noticeable delays. We will discuss a fast and robust method for online recognition of individual mathematical symbols. The method is based on the compact representation of parametric curves by the vector of coefficients of a truncated orthogonal polynomial series, which is computed on-line, as the curve is written. This vector is then classified using two distance measures: the Manhattan distance, which can be computed in a few machine instructions, is used for fast pre-classification among several hundred classes, and the distance to the convex hull of nearest neighbors for accurate tie-breaking.

Distance-based classification requires to store a database of samples from each symbol class. We reduce the storage requirements to about 600 KB by minimizing the number of coefficients per sample and the number of bits allocated per coefficient, as well as by choosing a subset of the most significant samples for each class.

This talk presents joint work with Stephen M. Watt and will be followed by an MKM presentation of a confidence measure developed for integrating the curve classifier into a recognizer of entire mathematical expressions.

We present a C library of in-place subroutines for univariate polynomial multiplication, division and GCD over L_p where L_p is an algebraic number field L with multiple field extensions reduced modulo a machine prime p. We assume elements of L_p and L are represented using a recursive dense representation. The key feature of our algorithms is that we eliminate the storage management overhead which is significant com- pared to the cost of arithmetic in Z_p by pre-allocating the exact amount of storage needed for both the output and working storage. We give an analysis for the working storage needed for each in-place algorithm and provide benchmarks demonstrating the efficiency of our library.

[full paper]

We present lazy and forgetful algorithms for multiplying and dividing multivariate polynomials. The lazy property allows us to compute the i-th term of a polynomial without doing the work required to compute all the terms. The forgetful property allows us to forget earlier terms that have been computed to save space. For example, given polynomials A,B,C,D,E we can compute the exact quotient Q = (A*B - C*D)/E without explicitly computing the numerator A*B-C*D which can be much larger than any of A,B,C,D,E and Q. As applications we apply our lazy and forgetful algorithms to reduce the maximum space needed by the Bareiss fraction-free algorithm for computing the determinant of a matrix of polynomials and the extended Subresultant algorithm for computing the inverse of an element in a polynomial quotient ring.

The original paper on the design of Maple was published in 1983 under the following title: "The design of Maple: A compact, portable and powerful computer algebra system." As this title implies, compactness was a design goal for Maple from the beginning. In this presentation, we take a retrospective view of the design goals as presented in the early papers. The fundamental design concept was to develop a compact kernel for the computer algebra system, implemented as compiled code, which handles the most basic arithmetic and algebraic operations and defines an interpreter for the user-level Maple language. The mathematical power of the computer algebra system is achieved via a large library of algorithms written in the Maple user language, to be loaded and interpreted on an as-needed basis. The most significant improvements in (space and time) efficiency are achieved by the development and implementation of better algorithms for the various mathematical tasks, and the ease of writing algorithms in the user-level Maple language facilitates the timely incorporation of new algorithms.

[Abstract in PDF ]