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:

It presents a program transformation that, given a numerical function F(x) defined by a program, creates a program that computes F[x0,x1], the first divided difference of F(x), where

  
                  / F(x0) - F(x1)
                 |  -------------                  if x0 != x1
                 |     x0 - x1 
     F[x0,x1] = <
                 |  d
                 |  --F(z), evaluated at z = x0    if x0 = x1
                  \ dz

It shows how computational first divided differencing generalizes computational differentiation.

It presents a second program transformation that permits the creation of higher-order divided differences of a numerical function defined by a program.

It shows how to extend these techniques to handle functions of several variables.

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.)