Multidimensional chains of recurrences

Abstract

A technique to expedite iterative computations which is based on multidimensional chains of recurrences MCR is presented. Algorithms for MCR construction, interpretation and MCR-based code generation are discussed. The notion of delayed MCR simpli cation introduced here for the rst time often leads to reduced times for both the MCR construction and MCR interpretation phases of this technique. Three di erent implementations of the MCR technique in Maple, C and Java are described.