Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-78c5997874-dh8gc Total loading time: 0 Render date: 2024-11-02T13:43:31.162Z Has data issue: false hasContentIssue false

21 - Reversal strategies for adjoint algorithms

Published online by Cambridge University Press:  06 August 2010

By
Laurent Hascoët
Edited by
Yves Bertot ,
Gérard Huet ,
Jean-Jacques Lévy  and
Gordon Plotkin
Laurent Hascoët
Affiliation:
INRIA Sophia-Antipolis Méditerranée
Yves Bertot
Affiliation:
INRIA-Sophia Antipolis, France
Gérard Huet
Affiliation:
Institut National de Recherche en Informatique et en Automatique (INRIA), Rocquencourt
Jean-Jacques Lévy
Affiliation:
Institut National de Recherche en Informatique et en Automatique (INRIA), Rocquencourt
Gordon Plotkin
Affiliation:
University of Edinburgh
Get access

Summary

Abstract

Adjoint algorithms are a powerful way to obtain the gradients that are needed in scientific computing. Automatic differentiation can build adjoint algorithms automatically by source transformation of the direct algorithm. The specific structure of adjoint algorithms strongly relies on reversal of the sequence of computations made by the direct algorithm. This reversal problem is at the same time difficult and interesting. This paper makes a survey of the reversal strategies employed in recent tools and describes some of the more abstract formalizations used to justify these strategies.

Why build adjoint algorithms?

Gradients are a powerful tool for mathematical optimization. The Newton method for example uses the gradient to find a zero of a function, iteratively, with an excellent accuracy that grows quadratically with the number of iterations. In the context of optimization, the optimum is a zero of the gradient itself, and therefore the Newton method needs second derivatives in addition to the gradient. In scientific computing the most popular optimization methods, such as BFGS, all give best performances when provided gradients too.

In real-life engineering, the systems that must be simulated are complex: even when they are modeled by classical mathematical equations, analytic resolution is totally out of reach. Thus, the equations must be discretized on the simulation domain, and then solved, for example, iteratively by a computer algorithm.

Type
Chapter
Information
From Semantics to Computer Science
Essays in Honour of Gilles Kahn
 , pp. 489 - 506
Publisher: Cambridge University Press
Print publication year: 2009

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]M., Bücker, G., Corliss, P., Hovland, U., Naumann and B., Norris (eds). Automatic Differentiation: Applications, Theory, and Implementations. LNCSE. Springer, 2006. Selected papers from AD2004, Chicago, July 2004.Google Scholar
[2]A., Carle and M., Fagan. ADIFOR 3.0 overview. Technical Report CAAMTR-00-02, Rice University, 2000.Google Scholar
[3]G., Corliss, C., Faure, A., Griewank, L., Hascoët and U., Naumann (eds). Automatic Differentiation of Algorithms, from Simulation to Optimization. LNCSE. Springer, 2002. Selected papers from AD2000, Nice, June 2000.Google Scholar
[4]C., Faure and U., Naumann. Minimizing the tape size. In [3], chapter VIII, pp. 293–298. 2002.
[5]C., Faure and Y., Papegay. Odyssée User's Guide. Version 1.7. Technical report 224, INRIA, 1998.Google Scholar
[6]R., Giering. Tangent linear and Adjoint Model Compiler, Users manual. Technical report, 1997. http://www.autodiff.com/tamc.
[7]R., Giering and T., Kaminski. Generating recomputations in reverse mode AD. In [3], chapter VIII, pp. 283–291. 2002.
[8]A., Griewank. Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation. SIAM, Frontiers in Applied Mathematics, 2000.Google Scholar
[9]L., Hascoët. The Data-dependence Graph of Adjoint Programs. Research Report 4167, INRIA, 2001.Google Scholar
[10]L., Hascoët and M., Araya-Polo. The adjoint data-flow analyses: Formalization, properties, and applications. In [1], pp. 135–146. 2006.
[11]L., Hascoët, U., Naumann and V., Pascual. To-be-recorded analysis in reverse mode Automatic Differentiation. Future Generation Computer System, 21(8):1401–1417, 2005.Google Scholar
[12]L., Hascoët and V, Pascual. Tapenade 2.1 user's guide. Technical report 300, INRIA, 2004.Google Scholar
[13]U., Naumann. Optimal accumulation of Jacobian matrices by elimination methods on the dual computational graph. Mathematical Programming, Series A, 99(3):399–421, 2004.Google Scholar
[14]U., Naumann. Optimal Jacobian accumulation is NP-complete. Mathematical Programing, 2006. in press. Appeared online first.Google Scholar
[15]U., Naumann, J., Utke, A., Lyons and M., Fagan. Control flow reversal for adjoint code generation. In Proceedings of the Fourth IEEE International Workshop on Source Code Analysis and Manipulation (SCAM 2004), pp. 55–64. IEEE Computer Society, 2004.Google Scholar
[16]J., Nocedal and S.-J., Wright. Numerical Optimization. Springer, Series in Operations Research, 1999.Google Scholar
[17]J., Utke, A., Lyons and U., Naumann. Efficient reversal of the intraprocedural flow of control in adjoint computations. J. Syst. Softw., 79(9):1280–1294, 2006.Google Scholar
[18]J., Utke, U., Naumann, M., Fagan, et al. Open AD/F: A Modular, Open-source Tool for Automatic Differentiation of Fortran codes. Technical report ANL/MCS-P1230-0205, Argonne National Laboratory, 2006. Submitted to ACM TOMS.Google Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×