{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/66437"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/66437","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Compiling Fast Partial Derivatives of Functions Given by Algorithms","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:","abstract_html":"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:","abstract_has_math":false,"creators":["Speelpenning, Bert"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":[],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2014,"date_issued":"2014-12-13T18:02:14Z","date_published":"2014-12-13T18:02:14Z","updated_at":"2026-07-22T22:25:55Z","subjects":["Computer Science"],"languages":["eng"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(UMI)AAI8017989"],"render_values":[{"text":"(UMI)AAI8017989","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/66437","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:creator","label":"Author","values":["Speelpenning, Bert"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2014-12-13T18:02:14Z","10000-01-01","1980"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer Science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["eng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/66437","(UMI)AAI8017989"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["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.","Made available in DSpace on 2014-12-13T18:02:14Z (GMT). No. of bitstreams: 1 8017989.pdf: 2994301 bytes, checksum: 7ce410c08ec2b710d58f4979f8410895 (MD5) Previous issue date: 1980","Embargo set by: Seth Robbins for item 66615 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","80 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1980."]},{"key":"dc:title","label":"Title","values":["Compiling Fast Partial Derivatives of Functions Given by Algorithms"]}]}],"canonical_facts":{"dc:creator":["Speelpenning, Bert"],"dc:date":["2014-12-13T18:02:14Z","10000-01-01","1980"],"dc:description":["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.","Made available in DSpace on 2014-12-13T18:02:14Z (GMT). No. of bitstreams: 1 8017989.pdf: 2994301 bytes, checksum: 7ce410c08ec2b710d58f4979f8410895 (MD5) Previous issue date: 1980","Embargo set by: Seth Robbins for item 66615 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","80 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1980."],"dc:identifier":["http://hdl.handle.net/2142/66437","(UMI)AAI8017989"],"dc:language":["eng"],"dc:subject":["Computer Science"],"dc:title":["Compiling Fast Partial Derivatives of Functions Given by Algorithms"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:25:55Z"}