**Olaf Bachmann
Centre for Computer Algebra
Department of Mathematics
University of Kaiserslautern
Kaiserslautern, Germany
**

Chains of Recurrences (CRs) are a tool for expediting the evaluation
of elementary expressions over regular grids. CR based evaluations
of elementary expressions consist of 3 major stages: CR
construction, simplification, and evaluation. This paper addresses
CR simplifications. The goal of CR simplifications is to manipulate
a CR such that the resulting expression is more efficiently to
evaluate. We develop CR simplification strategies which take the
computational context of CR evaluations into account. Realizing that
it is infeasible to always optimally simplify a CR
expression, we give heuristic strategies which, in most cases,
result in a optimal, or close-to-optimal expressions. The
motivations behind our proposed strategies are discussed and the
results are illustrated by various examples.

- 1 Introduction
- 2 CRs and their Cost Index
- 3 Cost Index and CR simplifications
- 4 CR simplification strategies
- 5 Examples
- 6 Summary and Discussion
- 7 Acknowledgments
- Bibliography
- About this document ...