Reminder: PL seminar, 10/31, 1325 CS

["Thomas Reps" <reps@xxxxxxxxxxx>]

Due to late scheduling, the announcement for the following talk
did not make it to "Talks".  It will be held at 4:00 PM
on Wednesday, 10/31 in 1325 CS.

-----------------------------------------------------------------

             Computational Divided Differencing
             and Divided-Difference Arithmetics

                       Thomas W. Reps
                  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 talk 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.

 o We present 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,x1] =  (F(x0) - F(x1)) / (x0 - x1).

   We show how this transformation generalizes computational
   differentiation.

 o We present a second program transformation that permits the
   creation of higher-order divided differences of a numerical
   function defined by a program.

 o We show how to extend these techniques to handle functions of
   several variables.

The benefits gained from these results include the following:

 o Because divided differences are the basis for a wide variety of
   numerical techniques, including polynomial interpolation, numerical
   integration, and solving differential equations, this work could
   lead to more robust programs in scientific and graphics
   applications.

 o Finite differences on an evenly spaced grid can be used to quickly
   generate a function's values at any number of points that extend
   the grid.  Because finite differences on an evenly spaced grid can
   be obtained from divided differences on an evenly spaced grid, our
   techniques may be useful in graphics applications for quickly
   plotting a function.
 
[Joint work with Louis B. Rall (Univ. of Wisconsin).]