Effective Simplification of CR expressions

Olaf Bachmann
Centre for Computer Algebra
Department of Mathematics
University of Kaiserslautern
Kaiserslautern, Germany
obachman@mathematik.uni-kl.de

Abstract:

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.