Files in this item
Files  Description  Format 

application/pdf 8017989.pdf (3MB)  (no description provided) 
Description
Title:  Compiling Fast Partial Derivatives of Functions Given by Algorithms 
Author(s):  Speelpenning, Bert 
Department / Program:  Computer Science 
Discipline:  Computer Science 
Degree Granting Institution:  University of Illinois at UrbanaChampaign 
Degree:  Ph.D. 
Genre:  Dissertation 
Subject(s):  Computer Science 
Abstract:  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 (PARDIFF)y/(PARDIFF)x(,1),...,(PARDIFF)y/(PARDIFF)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. 
Issue Date:  1980 
Type:  Text 
Language:  English 
Description:  80 p. Thesis (Ph.D.)University of Illinois at UrbanaChampaign, 1980. 
URI:  http://hdl.handle.net/2142/66437 
Other Identifier(s):  (UMI)AAI8017989 
Date Available in IDEALS:  20141213 
Date Deposited:  1980 
This item appears in the following Collection(s)

Dissertations and Theses  Computer Science
Dissertations and Theses from the Dept. of Computer Science 
Graduate Dissertations and Theses at Illinois
Graduate Theses and Dissertations at Illinois