1 Heuristic simplification of polynomial CR expressions

Given CR a expression $\Phi$, we first isolate all polynomial CR sub-expressions of $\Phi$ and consider the simplification of each polynomial CR sub-expression independently. Since a CR simplification follows the CR construction, we may assume that the expressions considered are polynomial CR expressions whose leaves are simple, one - dimensional CRs.

Secondly, we determine the dimension of the polynomial CR expression and handle the simplification of one- and multi - dimensional CR expressions separately.

For both cases, the suggested simplification heuristic makes use of the degree of a polynomial CR expression, which is defined as follows:

$$\begin{array}{cl} Deg(\Phi, x_k) \!\!&\!\! \mbox{ Condition}... ... n\cdot Deg(\Phi_1,x_k) \!\!&\!\! \Phi = \Phi_1^n \end{array}$$

Based on this definition, we suggest a simplification algorithm for the one - dimensional case which is based on the observation that a one - dimensional polynomial CR expression $\Phi$ can be transformed into a polynomial CR of length $Deg(\Phi, x)$.

Algorithm CRPOLYSIMP1D$(\Phi)$

Input:

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

Output:

Simplified polynomial 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 $Deg(\Phi, x) < CI(\Phi)$ then

1.

Recursively simplify $\Phi$ by unconditionally applying the simplification rules (1) - (6) and return the resulting polynomial CR of length c_s;

(C)

else if $\Phi = \Phi_1 + \cdots + \Phi_k$ then

1.

Set $\Phi_j^\prime =$CRPOLYSIMP1D$(\Phi_j)$ for $1 \leq j \leq k$;

2.

Transform all constant or polynomial CRs among the returned $\Phi_j^\prime$ into one polynomial CR (or constant) by applying the rules (1) and (3) and return the resulting CR expression.

(D)

else if $\Phi = \Phi_1 \cdot \cdots \cdot \Phi_k$ then

1.

Set $\Phi_j^\prime =$CRPOLYSIMP1D$(\Phi_j)$ for $1 \leq j \leq k$;

2.

Transform all constant or polynomial CRs among the returned $\Phi_j^\prime$ into one constant or polynomial CR by applying the rules (6) and (4) and return the resulting CR expression.

(E)

else $\qquad$/* Now $\Phi = \Phi_1^n$ */

Set $\Phi =$CRPOLYSIMP1D$(\Phi_1)$ and return $\Phi^n$

Notice that (B) is the crucial step of this algorithm, since it determines whether or not the CR expression is fully expanded into a polynomial CR. This is also the only step where we might lose the optimality of the CR simplification. For example, if we consider the CR expression $\Phi = \{x_0 ,\, {\mbox{\texttt{+}}}\, ,h\}^{63} + \sum_{j=1}^{12} j \cdot \{x_0 ,\, {\mbox{\texttt{+}}}\, ,h\}^j$ and assume that W(<tex2html_verb_mark>26<tex2html_verb_mark>) = 1 then $CI(\Phi) = 2 \lfloor \log_2 63 \rfloor + \sum_{j=1}^{12}(2 + 1\lfloor \log_2 j \rfloor) = 84$, $Deg(\Phi) = 63$, and hence, $\Phi$ is simplified into a polynomial CR of length 63, i.e., $CI(\Phi^\prime) = 63$. However, a simplification into $\Phi^\prime = \{x_0 ,\, {\mbox{\texttt{+}}}\, ,h\}^{63} + \{\varphi_1 ,\, {\mbox{\texttt{+}}}\, ,\ldots ,\, {\mbox{\texttt{+}}}\, ,\varphi_{12}\}$ would yield $CI(\Phi^\prime) = 33$, which is better. However, such cases could only be remedied by backtracking algorithms which, by their very nature, have a (worst-case) exponential time complexity.

The heuristic simplification of n-dimensional polynomial CR expressions is similar to the one - dimensional case. However, in addition to determining whether or not to expand the expression into a polynomial CR, we also have to determine a variable ordering for the expansion. Furthermore, we have to take the complexity of the evaluation grid into consideration, since the CI of multi - dimensional CR expressions depends on the number of evaluation points for each variable.

Algorithm CRPOLYSIMPND $(\Phi, {\bf m})$

Input:

Polynomial CR expression $\Phi$ with $X(\Phi) \subseteq \{x_1, \ldots, x_n\}$, ${\bf m} \in {\bf N}^n$

Output:

Simplified polynomial 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 $X(\Phi) = {x_k}$ then return CRPOLYSIMP1D$(\Phi)$;

(C)

Let $J = (j_1, \ldots, j_s)$ be a tuple of s integers, such that $\{x_{j_1}, \ldots, x_{j_s}\} = X(\Phi)$ and for all $1 \leq k < s$: d_jk < d_j<<547>>k+1 or d_jk = d_j<<549>>k+1 and $m_{j_k} \geq m_{j_{k+1}}$, where $d_{j_k} = Deg(\Phi, x_{j_k})$;

(D)

If $d_{j_1} + \frac{1}{m_{j_1}}(d_{j_2} + \frac{1}{m_{j_2}}(d_{j_3}+ \ldots )) \leq CI(\Phi, {\bf m})$ then

1.

Recursively simplify $\Phi$ by unconditionally applying the simplification rules (1) - (6) with the variable ordering $x_{j_1} > x_{j_2} > \cdots > x_{j_n}$ and return the result.

(C)

else if $\Phi = \Phi_1 + \cdots + \Phi_k$ then

1.

Set $\Phi_j^\prime =$CRPOLYSIMPND$(\Phi_j)$ for $1 \leq j \leq k$;

2.

Merge constant or polynomial CRs among the returned $\Phi_j^\prime$ as much as possible by applying the rules (1) and (3) and return the resulting CR expression.

(D)

else if $\Phi = \Phi_1 \cdot \cdots \cdot \Phi_k$ then

1.

Set $\Phi_j^\prime =$CRPOLYSIMPND$(\Phi_j)$ for $1 \leq j \leq k$;

2.

Merge constants or one - dimensional polynomial CRs among the returned $\Phi_j^\prime$ as much as possible by applying the rules (6) and (4) and return the resulting CR expression.

(E)

else $\qquad$/* Now $\Phi = \Phi_1^n$ */

Set $\Phi =$CRPOLYSIMPND$(\Phi_1)$ and return $\Phi^n$

Notice that the variable ordering is determined in step (C). Our heuristic for determining this ordering is based on the observation that for any variable ordering $x_{i_1} > x_{i_2} > \cdots > x_{i_s}$, $CI(\Phi^\prime) \leq d_{i_1} + \frac{1}{m_{i_1}}(d_{i_2} + \frac{1}{m_{i_2}}(d_{i_3}+ \ldots ))$. Hence, by choosing the variable ordering $x_{j_1} > x_{i_2} > \cdots > x_{j_s}$ as done in step (C), we minimize the upper bound for the CI of the respective fully expanded polynomial CR.

Various small and tedious to describe, but more or less obvious improvements to the algorithm above should be added. For example, in step C.1 (resp. D.1), we should collect all $\Phi_{k_1}, \ldots, \Phi_{k_j}$ for which $X(\Phi_{k_1}) = \ldots = X(\Phi_{k_j})$ and call the algorithm recursively with the expressions $\Phi_{k_1} + \cdots \Phi_{k_j}$ as arguments (provided they are different from $\Phi$) instead of calling the algorithm recursively with each single $\Phi_k$ as argument. This way, we enable a finer grained simplification of CR expressions which contains the same variables.

Let us look at some examples by considering the simplification of two-dimensional polynomial CR expressions over the variables x and y: To simplify our notation, let us write x for the CR $\{x_0 ,\, {\mbox{\texttt{+}}}\, ,h_x \}_{x}$, y for the CR $\{ y_0 ,\, {\mbox{\texttt{+}}}\, ,h_y \}_{y}$, and x_l (resp. y_l) for a CR of the form $\{\varphi_0 ,\, {\mbox{\texttt{+}}}\, , \varphi_1 ,\, {\mbox{\texttt{+}}}\, ,\ldots ,\, {\mbox{\texttt{+}}}\, ,\varphi_l\}_{x}$ for some constants $\varphi_0, \ldots, \varphi_l$. Furthermore, let us suppose that ${\bf m} = (100,100)$ and that W(<tex2html_verb_mark>27<tex2html_verb_mark>) = 1. Then each entry in table 2 shows a two-dimensional CR expression with its CI. Column 1 shows the unsimplified CR expression, column 2 and 3 show the fully-expanded polynomial CRs with the variable ordering x>y and y>x, respectively. Column 4 shows the CR expression returned by the algorithm CRPOLYSIMPND and column 5 shows the respective CR expression with the minimal CI.

  

Table 2: Examples for simplifications of two-dimensional polynomial CR expressions

Obviously, the larger the degree of the CR expressions, the larger the difference between the various simplification methods. However, the examples in table 2 already illustrate that a simplification algorithm which would fully expand a given CR expression (using any variable ordering) is inferior to CRPOLYSIMPND, and that CRPOLYSIMPND is not as good as the exhaustive search simplification algorithm.