4 CR simplification strategies

Evaluating the results of table 1 we see that for most rules we can not decide a priori whether they are CI reducing. Therefore, the previously suggested CR simplification algorithms ([#!us:issac94!#], [#!me:hisc!#], [#!zima:srr!#], [#!zima:issac95!#]) which recursively traverse the parse tree of a CR expression from the bottom to the top and unconditionally apply the simplification rules, do not, in general, result in a CR expression with a minimal CI.

An obvious algorithm which solves this problem is based on the observation that there are only finitely many CR expressions into which a given CR expression can be transformed by applications of the transformation rules of table 1. Hence, for a first, straight-forward approach, we may use an exhaustive search algorithm which, informally speaking,

- works on lists of CR expressions and recursively obtains
*all*CR expressions into which each CR expression of the current list can be transformed - if a CR simplification rule can be applied to the top node of the CR expression currently under consideration, then return a list of the expressions obtained by not applying the rule, by applying the rule, and, possibly, by applying the rule with a different variable ordering

Unfortunately, as might be expected, this algorithm has a (worst case) exponential time and space complexity w.r.t. the number of nodes of the given CR expression. Therefore its usage is limited to applications in which the CR simplification time does not contribute to the overall evaluation time (e.g., to source code generation and optimization problems) and to computational contexts with ample computing resources (especially memory).

However, a majority of applications require ``on-the-fly'' evaluations
of elementary expressions (e.g., visualization of mathematical objects,
see [#!us:ip!#]).
Hence, if we use the CR method for such computations, then the CR
simplification time counts towards the overall evaluation time.
Consequently, it is necessary to develop an alternative to the
exhaustive search simplification algorithm. The goal of such an
alternative algorithm is to balance the time spent during
simplifications with the time saved in the following evaluations. In
other words, we may not expect the algorithm to always find the CR
expression with the minimum CI. Instead, we may expect that the
algorithm simplifies a CR expression in a reasonable time (i.e., in at
most polynomial time) such that the CI of the resulting CR expression
is *close* to the minimum. To accomplish this goal, we need to
make some ad-hoc decisions which are based on experience and
observations, instead of strict reasoning. We refer to the following
simplification as a simplification heuristic.

The first heuristic decision is based on the observation that exponential CRs are obtained by transformations of polynomial CRs and that there is only one rule which transforms an exponential CR back into a polynomial CR (rule (7)). Therefore, we suggest arranging CR simplification in two independent passes: The first pass accomplishes the simplification of all polynomial CR (sub-) expressions, and the second pass considers the simplification of exponential CRs.

- 1 Heuristic simplification of polynomial CR expressions
- 2 Heuristic simplification of exponential CR expressions