×

zbMATH — the first resource for mathematics

Term graphs for computing derivatives in imperative languages. (English) Zbl 1278.68042
Mackie, Ian (ed.), Proceedings of the 3rd international workshop on term graph rewriting (TERMGRAPH 2006), Vienna, Austria, April 2006. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 176, No. 1, 99-111 (2007).
Summary: Automatic differentiation is a technique for the rule-based transformation of a subprogram that computes some mathematical function into a subprogram that computes the derivatives of that function. Automatic differentiation algorithms are typically expressed as operating on a weighted term graph called a linearized computational graph. Constructing this weighted term graph for imperative programming languages such as C/C++ and Fortran introduces several challenges. Alias and definition-use information is needed to construct term graphs for individual statements and then combine them into one graph for a collection of statements. Furthermore, the resulting weighted term graph must be represented in a language-independent fashion to enable the use of AD algorithms in tools for various languages. We describe the construction and representation of weighted term graphs for C/C++ and Fortran, as implemented in the ADIC 2.0 and OpenAD/F tools for automatic differentiation.
For the entire collection see [Zbl 1273.68037].
MSC:
68N15 Theory of programming languages
65D25 Numerical differentiation
68Q42 Grammars and rewriting systems
68R10 Graph theory (including graph drawing) in computer science
Software:
ADIC; ADOL-C; OpenAD; OpenAD/F
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ariola, Z.M.; Klop, J.W.; Plump, D., Bisimilarity in term graph rewriting, Inf. comput., 156, 2-24, (2000) · Zbl 1045.68590
[2] Baur, W.; Strassen, V., The complexity of partial derivatives, Theoretical computer science, 22, 317-330, (1983) · Zbl 0498.68028
[3] Bischof, C.H., P.D. Hovland and B. Norris, Implementation of automatic differentiation tools, Higher-Order and Symbolic Computation (2006), to appear
[4] Griewank, A., On automatic differentiation, (), 83-108
[5] Griewank, A., Evaluating derivatives: principles and techniques of algorithmic differentiation, Frontiers in appl. math., Number 19, (2000), SIAM Philadelphia, PA · Zbl 0958.65028
[6] Griewank, A.; Juedes, D.; Utke, J., ADOL-C, a package for the automatic differentiation of algorithms written in C/C++, ACM trans. math. software, 22, 131-167, (1996) · Zbl 0884.65015
[7] Griewank, A.; Reese, S., On the calculation of Jacobian matrices by the Markowitz rule, (), 126-135 · Zbl 0782.65027
[8] Hovland, P.D.; Naumann, U.; Norris, B., An XML-based platform for semantic transformation of numerical programs, (), 530-538
[9] Kreaseck, B.; Ramos, L.; Easterday, S.; Strout, M.; Hovland, P., Hybrid static/dynamic activity analysis, (), 582-590, also as ANL preprint
[10] Naumann, U., Min-ops derivative computation is NP-complete, Presentation at 2nd European Workshop on Automatic Differentiation
[11] Naumann, U., “Efficient Calculation of Jacobian Matrices by Optimized Application of the Chain Rule to Computational Graphs,” Ph.D. thesis, Technical University of Dresden (1999) · Zbl 0932.65019
[12] Naumann, U., Optimal accumulation of Jacobian matrices by elimination methods on the dual computational graph, Math. program., 99, 399-421, (2004) · Zbl 1084.68144
[13] Naumann, U., The complexity of derivative computation, Technical Report AIB-2005-15, RWTH Aachen (2005)
[14] Naumann, U.; Gottschling, P., Simulated annealing for optimal pivot selection in Jacobian accumulation, (), 83-97 · Zbl 1161.90473
[15] Norris, B.; Melfi, S., ADIC web server (2000)
[16] Plump, D., Term graph rewriting, Technical Report CSI-R9822, Computing Science Institute, Catholic University of Nijmegen (1998) · Zbl 0903.68108
[17] Strout, M.M., J. Mellor-Crummey and P. Hovland, Representation-independent program analysis, in: Proceedings of the Sixth ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE), 2005, pp. 67-74
[18] Utke, J., Openad web site
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.