Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Automated simplification of large symbolic expressions
Bailey D., Borwein J., Kaiser A. Journal of Symbolic Computation60 120-136,2014.Type:Article
Date Reviewed: Nov 19 2014

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.

Reviewer:  Alasdair McAndrew Review #: CR142952 (1502-0176)
Bookmark and Share
  Editor Recommended
Featured Reviewer
Simplification Of Expressions (I.1.1 ... )
Would you recommend this review?
Other reviews under "Simplification Of Expressions": Date
Symbolic computation of derivations using labelled trees
Grossman R., Larson R. Journal of Symbolic Computation 13(5): 511-523, 1992. Type: Article
Feb 1 1994
Understanding expression simplification
Carette J.  Symbolic and algebraic computation (Proceedings of the 2004 International Symposium on Symbolic and Algebraic Computation, Santander, Spain, Jul 4-7, 2004)72-79, 2004. Type: Proceedings
Dec 3 2004

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy