3 Cost Index and CR simplifications

Table 1 lists the major rules for simplifying multi - dimensional CR expressions. Most of these are generalizations of the rules given in [#!us:issac94!#,#!me:hisc!#,#!zima:issac95!#] from one- or two-dimensional CR expressions to multi - dimensional CR expressions. For a more detailed description and a proofs of these rules, see [#!me:thesis!#].

The left hand sides (LHS) of the simplification rules are given in column 2 and the respective right hand sides (RHS) are given in column 3. For reasons of clarity, the trivial simplification rules for general CR expressions based on the ring axioms are not shown.

In general, the difference
*CI*(*LHS*) - *CI*(*RHS*) is dependent on the
complexity of the regular grid, on the weights of the operations
involved, and on a chosen variable ordering. Column 4 marks the cases
where
*CI*(*LHS*)-*CI*(*RHS*) > 0 independently of all of these factors (the
symbol
is used to mark the rules where
*CI*(*LHS*)-*CI*(*RHS*) > 0 can
not be decided a priori). Column 5 shows
*CI*(*LHS*) - *CI*(*RHS*) of one -
dimensional CR expressions for which this difference depends at most
on the weights of the operations involved.

For one - dimensional CRs, the application of a simplification rule is
always unique in the sense that the same rule can not be applied to
the same CR expression and yield different simplification
results. However, this is, in general, not the case for
multi - dimensional CRs. Let us illustrate this by an example: Let
and
and consider
.
Then by (6),
i.e., by

with , we can simplify to

and alternatively to

where

Hence, if

More generally, the freedom of choosing a variable ordering implies an additional degree of freedom in applying certain simplification rules which consequently has an impact on the CI of the simplified CR expression. Column 6 of table 1 marks all simplification rules to which this applies with the symbol .