Computational Divided Differencing and Divided-Difference Arithmetics

Thomas W. Reps and Louis B. Rall
University of Wisconsin

Tools for computational differentiation transform a program that computes a numerical function F(x) into a related program that computes F'(x) (the derivative of F). This paper describes how techniques similar to those used in computational-differentiation tools can be used to implement other program transformations---in particular, a variety of transformations for computational divided differencing. The specific technical contributions of the paper are as follows:

The paper also discusses how computational divided-differencing techniques could lead to faster and/or more robust programs in scientific and graphics applications.

Finally, the paper describes how computational divided differencing relates to the numerical-finite-differencing techniques that motivated Robert Paige's work on finite differencing of set-valued expressions in SETL programs.

Dedicated to the memory of Robert Paige, 1947-1999.

(Click here to access the paper: PostScript, PDF.)