%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% 
%%% File: abstract.tex 
%%% Purpose: abstract for Ph. D. thesis 
%%% Olaf Bachmann, obachman@mcs.kent.edu, KSU, 1996 
%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\abstract

This dissertation considers algorithmic improvements and efficient
implementation techniques for the computational task of evaluating
elementary expressions over regular grids. Informally speaking,
elementary expressions are mathematical expressions built from
constants, variables and elementary function symbols and regular
grids are sets of evaluation points which are spaced regularly.

Evaluations of elementary expressions over regular grids occur
frequently in both numeric and symbolic computations: for example, in
visualizations of mathematical functions and
visualizations of objects which are specified by mathematical
expressions (like those in Computer Aided Design system), computations
of sums and products of functions, finite element analysis systems,
numeric integration and differential equation solvers, and many more.


The main idea behind the Chain of Recurrences (CR) method
investigated in this dissertation is: Instead of computing from
scratch, an elementary expression can be evaluated at the next point
much faster by using its values at previous points. That is, based on
the given elementary expression and the relation of the evaluation
points, we construct an equivalent Chains of Recurrences expression,
whose evaluation recursively connects consecutive evaluation
values. Depending on the given elementary expressions and regular
grid, CR-based evaluations can result in significant efficiency
increases. Speed-ups in the range of 100 or even 1000 w.r.t.
conventional evaluations methods are not unusual.

The main contribution of this thesis are a precise and general
formulation of the concepts and of the CR method, new
algorithms for constructing, simplifying, and evaluating
CR expressions, a numeric stability analysis of CR evaluations, and a
stand-alone and flexible implementation of the CR method.