This month, we will take a first look at ‘simplifying’ expressions and the some of the primary differences in how humans do it by hand versus how it is done when humans coax a machine to do it by manipulating a machine representation.
I’ve had occasion, when starting this series of blog posts, to reference Peter Norvig’s Paradigms of Artificial Intelligence Programming: Case Studies in Common LISP and I’ll do so again
According to the Mathematics Dictionary (James and James 1949), the word “simplified” is “probably the most indefinite term used seriously in mathematics.” The problem is that “simplified” is relative to what you want to use the expression for next. Which is simpler, $x^2 + 3x + 2$ or $(x-1)(x-2)$? The first makes it easier to integrate or differentiate, the second easier to find roots. We will be content to limit ourselves to “obvious” simplifications. For example, $x$ is almost always preferable to $1x+0$.
Last month’s examination of the complexities associated with traversing the tree with the goal of factoring a subexpression, although the approach was optimal, illustrates some of the difficulties. In fact, those difficulties are the tip of the iceberg for what is a subdiscipline in computer science that is called term rewriting.
Term rewriting is a mathematically sophisticated and subtle subject and, for this installment at the least, we will confine ourselves to the built-in functions provided by SymPy for performing term rewriting that happens largely without direct involvement from the user and can be said to fall under the heading of simplification. For the purposes of this discussion, simplification is defined as a method for generally making the number of terms in an expression go down and it should be held in contrast to expansion that generally makes the number of terms go up.
As an example, consider the tree expressions for the example Norvig provides. The tree for $x^2 + 3x + 2$ looks like
with seven nodes. The corresponding tree for $(x-1)(x-2)$ looks like
with 6 nodes. So there is a savings in terms of tree representation even though there are more typographical symbols needed in rendering $(x – 1)(x – 2)$ (eight of them, ignoring whitespace) versus $x^2 + 3x + 2$ (seven of them, ignoring white space and the ‘^’ used to typeset the exponent). The point of this somewhat whimsical discussion is that simplification is not only a matter of utility (what Norvig describes as ‘relative to what you want to use the expression for next’) but also of aesthetics.
In any event, there are at least 11 specialized simplification methods in SymPy. The following table lists them (with much of the verbiage taken from the help pages), their nominal purpose, and an example of each.
| Method | Purpose | Example |
|---|---|---|
| cancel | Takes any rational function and puts it into the standard canonical form, $p/q$, where $p$ and $q$ are expanded polynomials with no common factors. | $\text{cancel}\left( \frac{x^2 + 2*x +1}{x^2 + x} \right)$ $= \frac{x+1}{x}.$ |
| collect | Collects common powers of a term in an expression. | $\text{collect} \left(x^3 -z x^2 + 2 x^2 + x y + x – 3 \right)$ $= x^3 + x^2(2-z) + x(y+1) – 3$ |
| combsimp | Simplifies combinatorial expressions involving factorials and binomial coefficients; the symbols need to be integers (generalization to real numbers is found under gammasimp below). Used in conjunction with the factorial and binomial expressions | $\text{combsimp} \left( \frac{n!}{(n-3)!} \right) = n(n – 1)(n – 2)$ $\text{combsimp} \left( \frac{\binom{n+1}{k+1}}{\binom{n}{k}} \right) = \frac{n+1}{k+1}$ |
| factor | Takes a polynomial and factors it into irreducible factors over the rational numbers | $\text{factor}\left(x^2 z + 4 x y z + 4 y^2 z \right)$ $=z(x + 2y)^2$ |
| factorlist | Returns a more structured output of the factors | $\text{factor}\left(x^2 z + 4 x y z + 4 y^2 z \right)$ $= (1, [(z, 1), (x + 2y, 2)])$ |
| gammasimp | Simplifies expressions with gamma functions (using SymPy’s gamma) or combinatorial functions with non-integer argument | $\text{gammasimp} \left( \Gamma(x) \Gamma(1 – x) \right)$ $= \frac{\pi}{\sin(\pi – x)}$ |
| logcombine | Applies logarithm identities $log(xy)$ $= log(x)$ $+ log(y)$ and $log(x^n)$ $= n log(x)$ subject to certain assumptions on $x$ and $y$ (such as true for $x$ and $y$ being real and generally false for $x$ and/or $y$ complex). logcombine has a way to force the application to ignore assumptions using the ‘force=True’ optional argument. | $\text{logcombine} \left( \log (x) + \log (y) \right)$ $= \log (x y)$ and $\text{logcombine}( n \log(x) )$ $= \log \left( x^n \right)$ |
| powdenest | Applies the exponential identity $(x^a)^b = x^{ab}$ subject to the assumptions on $b$ (true if $b$ is an positive integer). powdenest has a way to force the application to ignore assumptions using the ‘force=True’ optional arguments. | $\text{powdenest} \left( \left(z^a\right)^b \right) = z^{ab}$ |
| powsimp | Applies the exponential identities $x^a x^b$ $= x^{a+b}$ (always true) and $x^a y^a$ = $(x y)^a$ (true if $x, y \geq 0$ and $a$ real | $\text{powsimp} \left( x^a x^b \right)$ $= x^{a+b}$ $\text{powsimp} \left( x^a y^a \right) = (x y) ^ a$ |
| radsimp | Rationalizes the denominator by removing square roots. | $\text{radsimp} \left( \frac{(2 + 2 \sqrt{2})x + (2 + \sqrt{8})y)}{2 + \sqrt{2}} \right)$ $= \sqrt{2} (x + y)$ |
| ratsimp | Puts an expression over a common denominator, cancel and reduce. | $\text{ratsimp} \left( \frac{1}{x} + \frac{1}{y} \right) = \frac{x+y}{xy}$ |
| together | Takes an expression or a container of expressions and puts it (them) together by denesting and combining rational subexpressions – often looks similar to ratsimp but it seems to be more general. | $\text{together} \left( \frac{1}{1+1/x} + \frac{1}{1+1/y} \right)$ $ = \frac{ x (y + 1) + y (x + 1)}{(x + 1)(y + 1)}$ |
| trigsimp | Simplifies expressions using trigonometric identities; works with hyperbolic trig functions; uses heuristics to find the “best” one | $\text{trigsimp} \left( 2 sin(x)^2 + 2cos(x)^2 \right) = 2$ |
Each of the functions above are building blocks in working through the steps of term rewriting. They represent common processes for specific steps. However, they are incapable of performing all the steps needed to simplify a generic expression. The generic function simplify “tries to apply intelligent heuristics to make the input expression “simpler”.” It is interesting to note that again the machine is far more brittle and unintelligent than an average human.
In subsequent blog posts, we’ll explore subs, replace, and xreplace methods within SymPy. These methods are the three ‘canonical’ methods within SymPy for rewriting terms that can be used in conjunction with the methods above to cover broader aspects of term rewriting.