2 Heuristic simplification of exponential CR expressions

The second pass of the heuristic simplification procedure is concerned with exponential CRs. Similar to the simplification of polynomial CRs, we first isolate all subexpressions of a CR expression which either already are, or could potentially be, transformed into an exponential CR and then deal with each of these expressions separately. Therefore, we may assume that the expressions which are to be simplified are CR expressions whose leaves are either already simplified polynomial CRs or are simple, one - dimensional exponential CRs.

Secondly, we once again treat the one - dimensional case differently from the n-dimensional case.

The simplification of one - dimensional exponential CR expressions is very similar to the simplification of one - dimensional polynomial CR expressions, except that we can not use the degree of an expression to predetermine its CI. Instead, we symbolically determine the structure of the exponential CR expression which is obtained by unconditionally applying all simplification rules and can then easily read its CI. Hence, the algorithm for simplifying one - dimensional exponential CR expressions proceeds as follows:

Algorithm CREXPSIMP1D$(\Phi)$

Input:

CR expression $\Phi$ with $X(\Phi) = \{x\}$

Output:

Simplified CR expression $\Phi^\prime$ with $CI(\Phi) \geq CI(\Phi^\prime)$

(A)

If $\Phi$ is a constant or a CR then return $\Phi$;

(B)

Let c_a be the CI of the expression which would be obtained from $\Phi$ by unconditionally applying the simplification rules (6) - (15).

(C)

If $c_a < CI(\Phi)$ then
Unconditionally apply the simplification rules (6) - (15) to $\Phi$ and return the result.

(D)

else $\qquad$ /* Now $\Phi = f \; \Psi_1 \ldots \Psi_{m}$ */
Return f CREXPSIMP1D $(\Psi_1) \ldots$CREXPSIMP1D $(\Psi_{m})$.

For example, if we are given the expression $\Phi = \sin\{2 ,\, {\mbox{\texttt{+}}}\, , 1 ,\, {\mbox{\texttt{+}}}\, ,-1\} \cdot 2^{\{0 ,\, {\mbox{\texttt{+}}}\, ,1\}}$, then to realize step (B) we symbolically apply all simplification rules and obtain the symbolic CR expression $\Re\{\psi_0 ,\, {\mbox{\texttt{*}}}\, ,\psi_1 ,\, {\mbox{\texttt{*}}}\, , \psi_2 \}$ which has a CI of c_s = 8 w_{<tex2htmlverbmark>28<tex2htmlverbmark>} + 4 w_{<tex2htmlverbmark>29<tex2htmlverbmark>}. Consequently, if $c_s < CI(\Phi) = 3w_{\verb*?+?} + w_{\verb*?sin?} + w_{\verb*?pow?}$ then we actually apply all simplification rules to $\Phi$ and return the results. Otherwise, we call the algorithm recursively on $\sin\{2 ,\, {\mbox{\texttt{+}}}\, ,1 ,\, {\mbox{\texttt{+}}}\, ,-1\}$ and $2^{\{0 ,\, {\mbox{\texttt{+}}}\, ,1\}}$ before returning the result.

We apply an even simpler strategy for n-dimensional exponential CR expressions by basing the decision whether or not to apply a simplification rule on local criteria, only. The reason for not taking properties of the entire expression into account is that the multi - dimensional polynomial CRs which are the leaves of the expression already predetermine the variable orderings, and furthermore greatly complicate the construction of symbolic expressions:

Algorithm CREXPSIMPND$(\Phi)$

Input:

Multi - dimensional, exponential CR expression $\Phi$.

Output:

Simplified CR expression $\Phi^\prime$ with $CI(\Phi) \geq CI(\Phi^\prime)$

(A)

If $\Phi$ is a constant or a CR then return $\Phi$;

(B)

If $\Phi$ is a one - dimensional CR expression return CREXPSIMP1D$(\Phi)$;

(D)

else $\qquad$ /* Now $\Phi = f \; \Psi_1 \ldots \Psi_{m}$ */

1.

Set $\Psi_j^\prime =$CREXPSIMPND$(\Phi_j)$ for $1 \leq j \leq n_k$;

2.

If one of the simplification rules (6) - (15) applies to $f \; \Psi_1^\prime \ldots \Psi_{m}^\prime$ such that the CI is reduced then apply the rule (if a choice of a variable ordering is involved, choose the one which results in the smaller CI) and recursively apply the algorithm to the coefficients of the obtained CR;

3.

else return $f \; \Psi_1^\prime \ldots \Psi_{m}^\prime$;