The Simplification Project
(Abstract)

Michael B. Monagan
Petr Lisonek

June 1998

Goals of the Project

The goal of this project is to develop new algorithms for simplifying formulae involving elementary and special functions in a computer algebra system and implement the design in Maple . The scope of this project includes:

Zero Recognition: Recognizing whether a given formula is equivalent to zero. This includes unevaluated integrals, sums, and products, as well as special functions, and it also includes the problem of branch cuts and domains.

Simplification of expressions with respect to a given measure of complexity. There are at least two measures of complexity that we want to take into account for the simplification purposes:
Syntactial complexity - size of the encoding of the expression.
Operational complexity - time needed for evaluating the expression after substitution(s). Here, we intuitively rank complexity of subexpressions according to the following: rational constant/function < algebraic constant/function < elementary function < special function < unevaluated integral or sum. (The concept of complexity measures is not present in Maple yet.)

Selected Examples

Global Simplification

> simplify(sinh(z) - (exp(z) - exp(-z))/2);

> assume(x,real);
simplify( sqrt(x^2)-abs(x));

The problem here is that simplify() operates locally, it does not recognize the global interaction of subexpressions. We need functionality that will facilitate this interaction.

Elementary Functions

The class of elementary functions is obtained by recursive applications of exponential and logarithmic extensions to a field of rational functions. Hence, it covers (among others) the trigonometric and hyperbolic functions etc. The Structure Theorem due to Risch can be used for zero recognition and simplification in this class.

> simplify( sin(u+v)-2*sin((u+v)/2)*cos((u+v)/2) );

> read `Risch/exp_log_simplify`:

> exp_log_simplify( sin(u+v)-2*sin((u+v)/2)*cos((u+v)/2) );

Inferred Assumptions

The assume() function of Maple allows one to assert that a certain variable can assume only a certain set of values. This knowledge can be used in simplification of expressions to properly select the branches etc. Moreover, the system should be able to infer such assumptions automatically.

In the following example, the sum() command makes an implicit assumption that is an integer. However, the result is not properly simplified under this assumption; the assumption has to be entered manually by the user.

> S:=sum((-1)^(n-k)*k^2,k=0..n);

> simplify(S);

> assume(n,integer);

> simplify(S);

Sums and Integrals

Simplification of sums and integrals is difficult in general; one can however try to merge expressions with common bounds etc. For example, the following sum is equal to 0:

> f:= t -> exp(-t^3):
int( f(t), t=a..b) + int( f(t), t=b..a);

> simplify(%);