Computer Algebra

Computer Algebra is the field of study that encompasses theorems, algorithms, data structures, and software design that make it possible for a computer to do symbolic calculations. As such, it overlaps with mathematics and computer science. The words 'algebra' and 'symbolic' are used to suggest that the computer can and does solve for x and is not limited to numeric computations.

Issues in Computer Algebra

• Simplification

  The notion of simplification is the intuitive one: given an expression, determine a simpler equivalent form. Thus x + x becomes 2x. Unfortunately, intuition only goes so far. When trying to formalize the notion of 'simple' one must pick a single form, which may not always be the desired simplification. Even with univariate polynomials it can be difficult to pick a 'simplified' form. For example, which is simpler: (x + 1)¹⁰⁰ or x¹⁰⁰ + ... + 1? If allowing multivariate polynomials, which is simpler: x + y or y + x? If allowing trigonometric functions, which of the following is the simplest equivalent form[ILC2005] of 1 -(1/4)sin²(2x)-sin²(2y)-cos⁴(x): sin(x + y)sin(x-y) or (1/2)(cos(2y)-cos(2x))?

  Often polynomial expansion is a useful simplified form. Computer algebra systems typically have a command to find this form; however, there are usually other simplification commands as well. A variation might involve expanding everything but sums raised to powers as in the first simplification example. Concerning the question what variable should come first, it is simple to pick an ordering, such as alphabetical order. However, again there are subtle issues. It seems that the Groebner basis computation is less efficient when using some orderings. Once trigonometric functions are introduced, pattern matching is the best approach.

• Algebraic Equation Solving

  A good place to start when solving an algebraic equation in one variable is to reduce to standard form and plug in to a formula. (Reduction to standard form is a kind of simplification, where left hand side of the equation is expanded and the right hand side is zero.) A simple equation solver based on this approach can be found here; more details of its implementation can be found in my paper Ideas Behind Computer Algebra and Their Use in the Classroom. However, when the degree of the left hand side is five or more there no longer exist formulas that involve only arithmetic and the extraction of roots. If numerical approximations are desired, there are fairly good iterative techniques that can be used to find the solutions. If exact solutions are desired, it may be possible to reduce the degree of the left hand side by searching for squared forms. Further, if the coefficients are rational numbers, there may be rational solutions, so it is worthwhile trying to factor the left hand side over the integers.

  Gaussian elimination is pretty good for solving systems of linear equations. For special cases such as sparse matrices or particularly dense matrices, other techniques may have an advantage.

  For non-linear systems, computing the Groebner basis yields an alternate equivalent system akin to what Gaussian elimination achieves for linear systems.

• Differentiation

  Algorithmic differentiation is not that difficult. The rules from introductory calculus can be directly translated into a program to compute the derivative of an expression. The difficult part is simplification. For example, one would like to avoid seeing 1•x + 1•x + 0 as the derivative of x•x + 5. Pattern matching can eliminate one times and zero plus, but may miss some simplifications. Polynomial representations can generate nicely simplified expressions with the caveat that they may do undesired expansion. The heuristic approach described above seems to be a good compromise for differentiation.

• Integration

  Algorithmic integration is difficult. Heuristic methods can often quickly find an anti-derivative given a simple expression. However, for complex expressions heuristic methods, such as those taught in first year calculus, can fail even when an anti-derivative exists. The starting point is the class of rational functions for which integration algorithms have existed for some time. An expression is then viewed as a function in an appropriate extension of the field of rational functions. Recursively integrating in successively smaller fields can determine whether an anti-derivative exists.

• Other Issues
  • Limits
  • Summation
  • Difference Equations
  • Ordinary Differential Equations
  • Partial Differential Equations
  • General Equation Solving

Annotated Bibliography

Abelson, Sussman. Structure and Interpretation of Computer Programs
This book is a wonderful introduction to computer science. It provides various practical techniques for managing the complexity of computer programs. There are many case studies including two computer algebra related programs: differentiation and polynomial arithmetic.

Baader, Nipkow. Term Rewriting and All That
Although computer algebra systems often use algebraic techniques, sometimes term rewriting is the best way to simplify an expression. This book focuses on the details of term rewriting and clearly discusses the issues of termination and confluence. Knuth-Bendix completion is discussed as is its connection Buchberger's algorithm for computing Groebner bases.

Bronstein. Symbolic Integration I: Transcendental Functions
This is the book for a detailed discussion of the theory and practice of algorithmic integration of transcendental functions.

Cox, Little, O'Shea. Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra
This book is simply an introduction to algebra. However, instead of the usual treatment, the focus is on multivariate polynomials and ideals. Thus Groebner bases are explained in only the second chapter.

Davenport, Siret, Tournier. Computer Algebra: Systems and Algorithms for Algebraic Computation
This book is a broad introduction to computer algebra as the title suggests; however, it is short and can be quite terse. Interestingly, the brevity often works in its favor; the authors often manage to explain a subtle concept in a single sentence. A broad range of topics is discussed: the representation of various mathematical objects, simplification of polynomial systems, advanced methods for GCDs (little space is given to elementary methods), algorithmic integration, and techniques for solving ordinary differential equations.

Geddes, Czapor, Labahn. Algorithms for Computer Algebra
This book is a solid introduction to computer algebra. It introduces the ideas of polynomial representation and polynomial algebra and goes on to discuss the issues involved in computing the GCD. It then goes on to discuss solutions of systems of linear and non-linear polynomial equations, and algorithmic integration. All of these discussions are methodical and to-the-point.

Graham, Knuth, Patashnik. Concrete Mathematics
This book is an alternative to the usual discrete math text. It includes a nice introduction to summation and goes on to describe a more advanced summation algorithm.

Knuth. The Art of Computer Programming Vol. 2: Seminumerical Algorithms
A classic computer science text. It includes algorithms and discussion concerning multi-precision integer arithmetic. It also includes an introduction to GCD computation and power series manipulation.

Norvig. Paradigms of Artificial Intelligence Programming: Case Studies in Common LISP
Although he is generally interested in artificial intelligence techniques, two of his case studies concern computer algebra. It is instructive to contrast the pattern-matching approach with the polynomial approach.

Petkovsek, Wilf, Zeilberger. A=B
The authors discuss the general question of how to decide if two terms are equal. They go on to focus on the various approaches to symbolic summation. The book concludes with a powerful algorithm to compute sums.

von zur Gathen, Gerhard. Modern Computer Algebra
This book is a general introduction to the subject. It also includes applications of computer algebra. The order of the material is unusual; it is grouped by the great mathematicians. Although the text is fairly thick, integration and summation do not receive a full treatment.

Zippel. Effective Polynomial Computation
Polynomial algorithms are crucial for computer algebra. This book focuses on that subject. It includes discussion of elementary notions of arithmetic on polynomials, as well as advanced algorithms for GCD and factoring.