The simplification of algebraic expressions is one of the major uses of any computer algebra system, and yet there is a paucity of material on the fundamental algorithms that underlie simplification. Such papers that exist tend to be quite old (ten years or more); some commercial systems shroud their inner workings in mystery, so that users are unable to know what’s going on. Almost any system will clam up on an expression that is complicated enough; throw in a few radicals, and you have an expression that may be theoretically simplifiable, but with which the system will be unable to cope.
This paper helps to address that issue by describing the design and implementation of a new algorithm for simplifying expressions of arbitrary complexity, by making (in part) use of the PSLQ integer relation algorithm. The PSLQ algorithm takes as input a list of complex numbers and tries to find a corresponding list of non-zero integers so that the linear combination of the complex numbers with the integers is zero. The authors show how repeated use of a variant of this algorithm can find relations between terms of an expression, leading to simpler expressions. Mathematica is used throughout as a source of examples and as the language of the paper’s algorithm, which can be downloaded from the third author’s website.
The paper includes careful descriptions of the algorithm, pseudocode for its components, and examples of large expressions (involving logarithms), which the algorithm is able to simplify. There are also examples of computations for which Mathematica produces output containing many hundreds of terms, which the new algorithm can shrink dramatically.
Written by two of the major workers in the field of computer algebra and a prize-winning graduate student, you would expect this paper to be first-class; it is indeed, in terms of its mathematics, its content, and its exposition.