Robin J. Hogan
Abstract
Gradient-based optimization problems are encountered in many fields, but the associated task of differentiating large computer algorithms can be formidable. The operator-overloading approach to performing reverse-mode automatic differentiation is the most convenient for the user but current implementations are typically 10-35 times slower than the original algorithm. In this paper a fast new operator-overloading method is presented that uses the expression template programming technique in C++ to provide a compile-time representation of each mathematical expression as a computational graph that can be efficiently traversed in either direction. Benchmarking with four different numerical algorithms shows this approach to be 2.6--9 times faster than current operator-overloading libraries, and 1.3--7.7 times more efficient in memory usage. It is typically less than 4 times the computational cost of the original algorithm, although poorer performance is found for all libraries in the case of simple loops containing no mathematical functions. An implementation is freely available in the Adept C++ software library.
- P. Aubert, N. Di Césaré, and O. Pironneau. Automatic differentiation in C++ using expression templates and application to a flow control problem. Comput. Vis. Sci. 3, 197--208. Google Scholar
Digital Library
- R. Bartlett, D. Gay, and E. Phipps. Automatic differentiation of C++ codes for large-scale scientific computing. In Proceedings of the International Conference on Computational Science (ICCS'06). Lecture Notes in Computer Science, vol. 3994, 525--532. Google ScholarDigital Library
- B. Bell. CppAD: A package for C++ algorithmic differentiation. http://www.coin-or.org/CppAD.Google Scholar
- C. Bendtsen and O. Stauning. FADBAD, a flexible C++ package for automatic differentiation.Tech. Rep. IMM-REP-1996-17, Technical University of Denmark.Google Scholar
- D. M. Gay. Semiautomatic differentiation for efficient gradient computations. In Automatic Differentiation: Applications, Theory, and Implementations, H. M. Bücker, G. F. Corliss, P. Hovland, U. Naumann, and B. Norris, Eds., Springer, 147--158.Google Scholar
- A. H. Gebremedhin, F. Manne, and A. Pothen. What color is your Jacobian? Graph coloring for computing derivatives. SIAM Rev. 47, 629--705. Google ScholarDigital Library
- R. Giering and T. Kaminski. Recipes for adjoint code construction. ACM Trans. Math. Softw. 24, 437--474. Google ScholarDigital Library
- A. Griewank and A. Walther. Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation 2nd Ed. SIAM. Google ScholarDigital Library
- A. Griewank, D. Juedes, and J. Utke. Algorithm 755: ADOL-C: A package for the automatic differentiation of algorithms written in C/C++. ACM Trans. Math. Softw. 22, 131--167. Google ScholarDigital Library
- R. J. Hogan. Fast lidar and radar multiple-scattering models -- 1. Small-angle scattering using the photon variance-covariance method. J. Atmos. Sci. 65, 3621--3635. Google ScholarDigital Library
- R. J. Hogan and A. Battaglia. Fast lidar and radar multiple-scattering models -- 2. Wide-angle scattering using the time-dependent two-stream approximation. J. Atmos. Sci. 65, 3636--3651. Google ScholarDigital Library
- P. D. Lax and B. Wendroff. Systems of conservation laws. Commun. Pure Appl. Math. 13, 217--237. Google ScholarDigital Library
- D. C. Liu and J. Nocedal. On the limited memory method for large scale optimization. Math. Programming B 45, 503--528. Google ScholarDigital Library
- U. Naumann. Optimal accumulation of Jacobian matrices by elimination methods on the dual computational graph. Math. Program. 99, 399--421. Google ScholarDigital Library
- E. Phipps and R. Pawlowski. Efficient expression templates for operator overloading-based automatic differentiation. In Recent Advances in Algorithmic Differentiation, Lecture Notes in Computational Science and Engineering, vol. 87, Springer. Google ScholarDigital Library
- O. B. Toon, R. P. Turco, D. Westphal, R. Malone, and M. S. Liu. A multidimensional model for aerosols: Description of computational analogues. J. Atmos. Sci. 45, 2123--2143.Google ScholarCross Ref
- T. Veldhuizen. Expression templates. C++ Report 7, 26--31. Google ScholarDigital Library
- M. Voßbeck, R. Giering, and T. Kaminski. Development and first applications of TAC++. In Advances in Automatic Differentiation, Lecture Notes in Computational Science and Engineering, vol. 64, Springer, 187--197.Google Scholar
- J. Willkomm and M. Bücker. AD tools from a user's perspective. In Proceedings of the 6th European AD Workshop. http://www.sc.rwth-aachen.de/willkomm/pdf/6th-euro-ad-willkomm.pdf.Google Scholar
Index Terms
- Fast Reverse-Mode Automatic Differentiation using Expression Templates in C++
Recommendations
Inferring differentiation pathways from gene expression
Motivation: The regulation of proliferation and differentiation of embryonic and adult stem cells into mature cells is central to developmental biology. Gene expression measured in distinguishable developmental stages helps to elucidate underlying ...
Variadic templates for C++
SAC '07: Proceedings of the 2007 ACM symposium on Applied computingGeneric functions and classes accepting a variable number of type arguments have proven to be a very useful, but missing, feature of C++. Numerous foundational libraries rely on clever template and preprocessor tricks to emulate such variadic templates. ...
Identification of microRNA activity by Targets' Reverse EXpression
Motivation: Non-coding microRNAs (miRNAs) act as regulators of global protein output. While their major effect is on protein levels of target genes, it has been proven that they also specifically impact on the messenger RNA level of targets. ...
Comments