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 $\Phi^\prime$ into which a given CR expression $\Phi$ 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

and, consequently, returns a list of all CR expressions $\Phi^\prime$ into which the given input CR expression $\Phi$ can be transformed. By computing the CI of each CR expression obtained we can then easily find the one with the minimal CI.

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.