skip to main content
article

A differentiation-enabled Fortran 95 compiler

Published: 01 December 2005 Publication History

Abstract

The availability of first derivatives of vector functions is crucial for the robustness and efficiency of a large number of numerical algorithms. An upcoming new version of the differentiation-enabled NAGWare Fortran 95 compiler is described that uses programming language extensions and a semantic code transformation known as automatic differentiation to provide Jacobians of numerical programs with machine accuracy. We describe a new user interface as well as the relevant algorithmic details. In particular, we focus on the source transformation approach that generates locally optimal gradient code for single assignments by vertex elimination in the linearized computational graph. Extensive tests show the superiority of this method over the current overloading-based approach. The robustness and convenience of the new compiler-feature is illustrated by various case studies.

References

[1]
Aho, A., Sethi, R., and Ullman, J. 1986. Compilers. Principles, Techniques, and Tools. Addison-Wesley, Reading, MA.
[2]
Averik, B., Carter, R., and Moré, J. 1991. The MINPACK-2 test problem collection (preliminary version). Tech. mem. ANL/MCS-TM-150. Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL.
[3]
Balay, S., Buschelman, K., Gropp, W., Kaushik, D., Knepley, M., Curfman-McInnes, L., Smith, B., and Zhang, H. 2003. PETSc 2.0 users manual. Tech. rep. ANL-95/11---revision 2.1.6. Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL. Go online to http://www.mcs.anl.gov/petsc.
[4]
Benson, S., McInnes, L., and Moré, J. 2000. TAO users manual. Tech. rep. ANL/MCS-TM-242, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL. Go online to www.mcs.anl.gov/tao.
[5]
Benson, S. and Moré, J. 2001. A limited memory variable metric algorithm for bound constrained minimization. Tech. rep. ANL/MCS-P909-0901. Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL.
[6]
Berz, M., Bischof, C., Corliss, G., and Griewank, A., Eds. 1996. Computational Differentiation: Techniques, Applications, and Tools. Proceedings Series. SIAM Press, Philadelphia, PA.
[7]
Bischof, C., Carle, A., Khademi, P., and Maurer, A. 1996. The ADIFOR 2.0 system for automatic differentiation of Fortran 77 programs. IEEE Comp. Sci. Eng. 3, 3, 18--32.
[8]
Bischof, C., Roh, L., and Mauer, A. 1997. ADIC---An extensible automatic differentiation tool for ANSI-C. Softw. Pract. Exper. 27, 12, 1427--1456.
[9]
Cohen, M., Naumann, U., and Riehme, J. 2003. Toward differentiation-enabled Fortran 95 compiler technology. In Proceedings of the 2003 ACM Symposium on Applied Computing. 143--147.
[10]
Corliss, G., Faure, C., Griewank, A., Hascoet, L., and Naumann, U., Eds. 2002. Automatic Differentiation of Algorithms---From Simulation to Optimization. Springer, New York, NY.
[11]
Corliss, G. and Griewank, A., Eds. 1991. Automatic Differentiation: Theory, Implementation, and Application. Proceedings Series. SIAM Press, Philadelphia, PA.
[12]
Curtis, A., Powell, M., and Reid, J. 1974. On the estimation of sparse Jacobian matrices. J. Inst. Math. Appl. 13, 117--119.
[13]
Forth, S., Tadjouddine, M., Pryce, J., and Reid, J. 2004. Jacobian code generated by source transformation and vertex elimination can be as efficient as hand-coding. ACM Trans. Math. Softw. 3, 30 (Sep.), 266--299.
[14]
Garey, M. and Johnson, D. 1979. Computers and Intractability---A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, San Francisco, CA.
[15]
Griewank, A. 2000. Evaluating Derivatives. Principles and Techniques of Algorithmic Differentiation. Number 19 in Frontiers in Applied Mathematics. SIAM Press, Philadelphia, PA.
[16]
Griewank, A. and Reese, S. 1991. On the calculation of Jacobian matrices by the Markovitz rule. In Corliss and Griewank {1991}, 126--135.
[17]
Hascoët, L., Naumann, U., and Pascual, V. 2004. TBR analysis in reverse-mode automatic differentiation. In Future Generation Computer Systems---Special Issue on Automatic Differentiation, M. Bücker, Ed. Elsevier, Amsterdam, The Netherlands.
[18]
Hopkins, T. and Phillips, C. 1988. Numerical Methods in Practice Using the NAG Library. International Computer Science Series. Addison-Wesley, Reading, MA.
[19]
Hovland, P., Norris, B., and Smith, B. 2002. Making automatic differentiation truly automatic: Coupling PETSc with ADIC. In Computational Science---ICCS 2002, Proceedings of the International Conference on Computational Science, Amsterdam, The Netherlands, April 21--24, 2002. Part II, P. M. A. Sloot, C. J. K. Tan, J. J. Dongarra, and A. G. Hoekstra, Eds. Lecture Notes in Computer Science, vol. 2330. Springer, Berlin, Germany, 1087--1096.
[20]
Moré, J. 2001. Automatic differentiation tools in optimization software. In Corliss et al. {2002}, 25--34.
[21]
Naumann, U. 2002. On optimal Jacobian accumulation for single-expression-use programs. Preprint ANL-MCS/P944-0402. Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL.
[22]
Naumann, U. 2004. Optimal accumulation of Jacobian matrices by elimination methods on the dual computational graph. Math. Prog. 99, 3 (Apr.), 399--421.
[23]
Naumann, U. and Riehme, J. 2005. Computing adjoints with the NAGWare Fortran 95 compiler. In Automatic Differentiation: Applications, Theory, and Tools, H. Bücker, G. Corliss, P. Hovland, U. Naumann, and B. Norris, Eds. Lecture Notes in Computational Science and Engineering, vol. 50. Springer, Berlin, Germany, 159--169.
[24]
Newsam, G. and Ramsdell, J. 1983. Estimation of sparse Jacobian matrices. SIAM J. Alg. Dis. Meth. 4, 404--417.
[25]
Roe, P. 1981. Approximating Riemann solvers, parameter vectors, and difference schemes. J. Comp. Physics 43, 357--372.
[26]
Tadjouddine, M., Forth, S., and Pryce, J. 2001. AD tools and prospects for optimal AD in CFD flux calculations. In Corliss et al. {2002}, 255--261.
[27]
Tadjouddine, M., Forth, S., Pryce, J., and Reid, J. 2002. Performance issues for vertex elimination methods in computing Jacobians using automatic differentiation. In Computational Science---ICCS 2002, Proceedings of the International Conference on Computational Science, Amsterdam, The Netherlands, April 21--24, 2002. Part II, P. Sloot, C. Tan, J. Dongarra, and A. Hoekstra, Eds. Lecture Notes in Computer Science, vol. 2330. Springer, Berlin, Germany, 1077--1086.
[28]
The Numerical Algorithms Group, 2000. NAG Fortran 90 library. Online documentation, Oxford, U.K., at http://www.nag.co.uk/numeric/FN/manual/html/FNlibrarymanual.asp.
[29]
The Numerical Algorithms Group, 2002. The NAG Fortran library manual, mark 20. Online documentation at http://www.nag.co.uk/numeric/fl/manual/html/FLlibrarymanual.asp.
[30]
Utke, J. 2005. Flattening basic blocks. In Automatic Differentiation: Applications, Theory, and Tools, H. Bücker, G. Corliss, P. Hovland, U. Naumann, and B. Norris, Eds. Lecture Notes in Computational Science and Engineering, vol. 50. Springer, Berlin, Germany, 121--133.
[31]
Utke, J. and Naumann, U. 2004a. Optimality-preserving elimination of linearities in Jacobian accumulation. Presentation at SIAM Workshop on Combinatorial Scientific Computing, San Francisco, February 2004. Article is under review for special issue on combinatorial scientific computing of the Electronic Transactions on Numerical Analysis (ETNA), dedicated to Professor Alan George.
[32]
Utke, J. and Naumann, U. 2004b. Separating language-dependent und independent tasks for the semantic transformation of numerical programs. In Software Engineering and Applications, M. Hamza, Ed. ACTA Press, Calgary, Alta., Canada (To appear).
[33]
Wengert, R. 1964. A simple automatic derivative evaluation program. Comm. ACM 7, 463--464.

Cited By

View all
  • (2016)The efficiency of geophysical adjoint codes generated by automatic differentiation toolsComputer Physics Communications10.1016/j.cpc.2015.10.008199(22-28)Online publication date: Feb-2016
  • (2016)First-order uncertainty analysis using Algorithmic Differentiation of morphodynamic modelsComputers & Geosciences10.1016/j.cageo.2015.10.01290:PB(144-151)Online publication date: 1-May-2016
  • (2015)Clad — Automatic Differentiation Using Clang and LLVMJournal of Physics: Conference Series10.1088/1742-6596/608/1/012055608(012055)Online publication date: 22-May-2015
  • Show More Cited By

Recommendations

Comments

Information & Contributors

Information

Published In

cover image ACM Transactions on Mathematical Software
ACM Transactions on Mathematical Software  Volume 31, Issue 4
December 2005
167 pages
ISSN:0098-3500
EISSN:1557-7295
DOI:10.1145/1114268
Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 2005
Published in TOMS Volume 31, Issue 4

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Source transformation
  2. preaccumulation

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)9
  • Downloads (Last 6 weeks)1
Reflects downloads up to 16 Feb 2025

Other Metrics

Citations

Cited By

View all
  • (2016)The efficiency of geophysical adjoint codes generated by automatic differentiation toolsComputer Physics Communications10.1016/j.cpc.2015.10.008199(22-28)Online publication date: Feb-2016
  • (2016)First-order uncertainty analysis using Algorithmic Differentiation of morphodynamic modelsComputers & Geosciences10.1016/j.cageo.2015.10.01290:PB(144-151)Online publication date: 1-May-2016
  • (2015)Clad — Automatic Differentiation Using Clang and LLVMJournal of Physics: Conference Series10.1088/1742-6596/608/1/012055608(012055)Online publication date: 22-May-2015
  • (2014)Estimation of Data Assimilation Error: A Shallow-Water Model StudyMonthly Weather Review10.1175/MWR-D-13-00205.1142:7(2502-2520)Online publication date: 27-Jun-2014
  • (2013)Rückrechnung von Rand- und Anfangsbedingungen mit Telemac und Algorithmischer DifferentiationReverse engineering of initial and boundary conditions with Telemac and algorithmic differentiationОбратный расчет предельных и исходных условий с использованием программного обеспечения Telemac и алгоритмической дифференциацииWASSERWIRTSCHAFT10.1365/s35147-013-0843-y103:12(22-27)Online publication date: 20-Nov-2013
  • (2012)CFD Development with Automatic Differentiation50th AIAA Aerospace Sciences Meeting including the New Horizons Forum and Aerospace Exposition10.2514/6.2012-573Online publication date: 14-Jun-2012
  • (2012)Combinatorial Problems in Algorithmic DifferentiationCombinatorial Scientific Computing10.1201/b11644-6(129-161)Online publication date: 29-Mar-2012
  • (2012)AD in Fortran: Implementation via PrepreprocessorRecent Advances in Algorithmic Differentiation10.1007/978-3-642-30023-3_25(273-284)Online publication date: 7-Jul-2012
  • (2010)New Algorithms for Optimal Online CheckpointingSIAM Journal on Scientific Computing10.1137/08074243932:2(836-854)Online publication date: Jan-2010
  • (2010)On the use of discrete adjoints in goal error estimation for shallow water equationsProcedia Computer Science10.1016/j.procs.2010.04.0131:1(107-115)Online publication date: May-2010
  • Show More Cited By

View Options

Login options

Full Access

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Figures

Tables

Media

Share

Share

Share this Publication link

Share on social media