Compiling Fast Partial Derivatives of Functions Given by Algorithms

80 p.Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1980.If the gradient of the function y = f(x(,1),...,x(,n)) is desired where f is given by an algorithm Af(x,n,y), most numerical analysts will use numerical differencing. This is a sampling scheme that approximates derivatives by the slope of secants in closely spaced points. Symbolic methods that make full use of the program text of Af should be able to come up with a better way to evaluate the gradient of f. The system "Jake" described in this thesis produces gradients significantly faster than numerical differencing. A system sketch of Jake is presented below:Jake can handle algorithms Af with arbitrary flow of control. If algorithm Af requires T time to evaluate y for given values of x(,1),...,x(,n), the algorithm Af' produced by Jake will evaluate the gradient (PAR-DIFF)y/(PAR-DIFF)x(,1),...,(PAR-DIFF)y/(PAR-DIFF)x(,n) in time O(T). In contrast, numerical differencing requires O(nT). The space requirements of Af' are modest. Measurements performed on one particular machine suggest that Jake is faster than numerical differencing for n > 8. Somewhat weaker results have been obtained for the problem of computing Jacobians of arbitrary shape.Jake is based on a view of an execution of the algorithm Af as a sequence of transformations in a state space. The Jacobian of the entire execution of the algorithm is the matrix product of the Jacobians for each individual transformation. The optimal multiplication order of these Jacobians leads to substantial savings over numerical differencing. In case of gradients (y being a scalar) these savings can be shown to be O(n). The algorithms Af and Af' in this approach are sufficiently close so that Af can be transformed into Af' by automatic means. Current compiler technology can be used to build a practical translator; no automatic theorem proving or heuristic search procedures are required.Numerical analysts currently hesitant to use methods of functional iteration requiring a knowledge of derivatives may find in Jake a tool making such methods the preferred ones.U of I OnlyRestricted to the U of I community idenfinitely during batch ingest of legacy ETD