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:
Before proceeding further, let us illustrate these stages by an example. Suppose we wish to evaluate the polynomial p(x) = 2x^{3} + x^{2} + x - 3 at the 1,001 points 0,.01,,9.99,10.0:
for i := 0 to 1,000 do odwhere contains the values of p at the points 0,.01,,9.99,10.0.
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)^{100} 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!#]):
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.