1 Introduction

Chains of Recurrence (CRs) address the problem of fast evaluations of elementary expressions over regular grids. Informally speaking, elementary expressions are expressions built from constants, variables, and elementary function symbols (e.g., rational or transcendental expressions) and a regular grid is a set of regularly spaced points (e.g., linearly spaced points on a line, points on the intersection of lines which are parallel to the coordinate axes, evenly distributed points on circles, ellipses, spheres, etc).

The main idea behind the CR method is: Instead of computing from scratch, an elementary expression can be evaluated at the next point much faster by using its values at previous points. That is, based on the given elementary expression and the relation of the evaluation points, we construct an equivalent CR expression, whose evaluation recursively connects consecutive evaluation values. CR expressions are similar to elementary expressions, except that Chains of Recurrences play the role of variables.

A CR based evaluation of an elementary expression F consists of three stages:

1.

The construction of a CR expression $\Psi$ which is equivalent to F.

2.

The simplification of $\Psi$.

3.

The evaluation of $\Psi$.

Before proceeding further, let us illustrate these stages by an example. Suppose we wish to evaluate the polynomial p(x) = 2x³ + x² + x - 3 at the 1,001 points 0,.01,$\ldots$,9.99,10.0:

1.

The CR expression $\Psi = 2\{0 ,\, {\mbox{\texttt{+}}}\, ,.01\}^3 + \{0 ,\, {\mbox{\texttt{+}}}\, ,.01\}^2 + \{0 ,\, {\mbox{\texttt{+}}}\, ,.01\} - 3$ is obtained from the CR construction. Notice that $\Psi$ is similar to p, except that each occurrence of x in p is replaced by the Chain of Recurrence $\{0 ,\, {\mbox{\texttt{+}}}\, ,.01\}$.

2.

$\Psi$ is simplified:

$$\begin{eqnarray*}\lefteqn{ 2\{0 ,\, {\mbox{\texttt{+}}}\, ,.01\}^3 + \{0 ,\, {\... ...ox{\texttt{+}}}\, ,.000112 ,\, {\mbox{\texttt{+}}}\, ,.000012\} \end{eqnarray*}$$

where all simplification steps are based on general simplification properties of CR expressions (see below).

3.

The CR $\{-3 ,\, {\mbox{\texttt{+}}}\, ,.010102 ,\, {\mbox{\texttt{+}}}\, ,.000112 ,\, {\mbox{\texttt{+}}}\, ,.000012\}$ is evaluated over 1,000 points by a procedure which is of the following form:

$\varphi_0:=-3; \; \varphi_1 := .010102; \; \varphi_2 := .000112; \; \varphi_3 := .000012;$ 
for i := 0 to 1,000  do
		 

$\Psi[i] := \varphi_0;$

$\varphi_0 := \varphi_0 + \varphi_1; \;\varphi_1 := \varphi_1 + \varphi_2; \;\varphi_2 := \varphi_2 + \varphi_3;$
od

where $\Psi[i]$ contains the values of p at the points 0,.01,$\ldots$,9.99,10.0.

We should notice that the evaluation of $\Phi[i]$ requires 3 additions per evaluation point. Therefore, compared with a Horner evaluation of p, we saved a total of 3,000 multiplications. Due to this saving and due to judicious implementation techniques, a CR based evaluation of p can be significantly faster than a ``normal'' Horner evaluation (for this example, a speedup of 200 is reported in [#!me:sigsam!#]).

In [#!me:thesis!#] algorithms for the construction and evaluation of multi - dimensional CRs are given, which assure that a CR based evaluation without simplification is at least as efficient as an evaluation of the given elementary expression. However, the true power, the ``salt in the soup'', of the CR method stems from the fact that certain classes of CR expressions (and hence, elementary expressions) can be simplified in such a way that evaluations of the resulting CR expression require significantly less arithmetic operations than the original expression, enabling a significant increase in the evaluation efficiency.

However, as with other simplifications, there is a major problem with CR simplifications, namely that of the evasive and context-dependent concept of ``simplicity'': As outlined in [#!loos:simp!#], simpler might mean ``closer to a canonical representation'', ``shorter'', ``needs less memory for a computer representation'', ``numerically more stable'', etc; some concepts of simplicity might be undecidable (e.g., that of the canonical simplification of transcendental expressions, see [#!loos:simp!#]) or computationally very expensive to realize (e.g., critical pair simplification algorithms); simplicity w.r.t. one concept might be diametric w.r.t. another concept (e.g. compare (x+1)¹⁰⁰ and its expanded canonical representation w.r.t. shortness); and so on.

Clearly, in our context ``simpler'' means ``can be evaluated more efficiently''. However, already this qualification is problematic, since it does not reflect some other, and often important, evaluation criteria, such as numeric stability, memory consumption, and the time spent for the simplification itself. But even the sole use of ``evaluation efficiency'' as a measure for simplicity is problematic: The evaluation efficiency of a given CR expression depends on many, possibly varying, factors, such as the complexity and location of the evaluation region (i.e., the regular grid), the underlying computational domain (e.g., floating point or arbitrary precision numbers), the used hard- and software platform, etc. In this paper we develop new simplification strategies which take these varying factors into account, thereby closing important gaps of previous works about CRs ([#!me:hisc!#,#!us:issac94!#,#!zima:srr!#,#!zima:issac95!#]):

• The previously suggested unconditional application of CR simplification rules leads to often very unsatisfiable results for more complex expressions (like those containing trigonometric functions, or high degree polynomials).
• The problem of the variable ordering of multi - dimensional CR expressions was not addressed.

The results given here are based on the partial solutions of this problem for the two-dimensional case, as described in [#!me:sigsam!#].

In the ideal case, we would like to find a simplification procedure that is optimal in the sense that it produces the CR expression that is the most efficient to evaluate, under consideration of all factors of the computational context. However, this is probably not realizable, given the complexity of such a task. Realistically, we can only hope for simplification results which are optimal or very close to optimal in most cases.

To achieve this goal, we introduce in Section 2 the concept of the Cost Index (CI) as an approximate measure of the efficiency of CR evaluations. This is followed an analysis of the effect of CR simplification rules on the CI of the transformed CR expression (Section 3). Based on this analysis, we develop CR simplification strategies in Section 4 and conclude this by considering an extended set of examples in Section 5.