1 Heuristic simplification of polynomial CR expressions

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:

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 can be transformed into a polynomial CR of length .

**Algorithm** CRPOLYSIMP1D

**Input:**- Polynomial CR expression with
**Output:**- Simplified polynomial CR expression with

**(A)**- If is a constant or a CR then return ;
**(B)**- If
then
- 1.
- Recursively simplify
by
unconditionally applying the simplification rules
(1) - (6) and return the resulting
polynomial CR of length
*c*_{s};

**(C)**- else if
then
- 1.
- Set CRPOLYSIMP1D for ;
- 2.
- Transform all constant or polynomial CRs among the returned into one polynomial CR (or constant) by applying the rules (1) and (3) and return the resulting CR expression.

**(D)**- else if
then
- 1.
- Set CRPOLYSIMP1D for ;
- 2.
- Transform all constant or polynomial CRs among the returned into one constant or polynomial CR by applying the rules (6) and (4) and return the resulting CR expression.

**(E)**- else /* Now
*/
- Set CRPOLYSIMP1D and return

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

**Input:**- Polynomial CR expression with ,
**Output:**- Simplified polynomial CR expression with

**(A)**- If is a constant or a CR then return ;
**(B)**- If then return CRPOLYSIMP1D;
**(C)**- Let
be a tuple of
*s*integers, such that and for all :*d*_{jk}<*d*_{j<<547>>k+1}or*d*_{jk}=*d*_{j<<549>>k+1}and , where ; **(D)**- If
then
- 1.
- Recursively simplify by unconditionally applying the simplification rules (1) - (6) with the variable ordering and return the result.

**(C)**- else if
then
- 1.
- Set CRPOLYSIMPND for ;
- 2.
- Merge constant or polynomial CRs among the returned as much as possible by applying the rules (1) and (3) and return the resulting CR expression.

**(D)**- else if
then
- 1.
- Set CRPOLYSIMPND for ;
- 2.
- Merge constants or one - dimensional polynomial CRs among the returned as much as possible by applying the rules (6) and (4) and return the resulting CR expression.

**(E)**- else /* Now
*/
- Set CRPOLYSIMPND and return

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 for which and call the algorithm recursively with the expressions as arguments (provided they are different from ) instead of calling the algorithm recursively with each single 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
,
*y* for the CR
,
and
*x*_{l} (resp. *y*_{l}) for a CR of the form
for some constants
.
Furthermore, let us suppose that
and that
*W*(<*tex*2*html*_{v}*erb*_{m}*ark*>27<*tex*2*html*_{v}*erb*_{m}*ark*>) = 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.

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.