An efficient overloaded implementation of forward mode automatic differentiation in MATLAB

ABSTRACT

The Mad package described here facilitates the evaluation of first derivatives of multidimensional functions that are defined by computer codes written in MATLAB. The underlying algorithm is the well-known forward mode of automatic differentiation implemented via operator overloading on variables of the class fmad. The main distinguishing feature of this MATLAB implementation is the separation of the linear combination of derivative vectors into a separate derivative vector class derivvec. This allows for the straightforward performance optimization of the overall package. Additionally, by internally using a matrix (two-dimensional) representation of arbitrary dimension directional derivatives, we may utilize MATLAB's sparse matrix class to propagate sparse directional derivatives for MATLAB code which uses arbitrary dimension arrays. On several examples, the package is shown to be more efficient than Verma's ADMAT package [Verma 1998a].

REFERENCES

• 1: Berz, M., Bischof, C., Corliss, G., and Griewank, A., Eds. 1996. Computational Differentiation: Techniques, Applications, and Tools. SIAM, Philadelphia, PA.
• 2: C. H. Bischof , H. M. Bücker , B. Lang , A. Rasch , A. Vehreschild, Combining Source Transformation and Operator Overloading Techniques to Compute Derivatives for MATLAB Programs, Proceedings of the Second IEEE International Workshop on Source Code Analysis and Manipulation (SCAM'02), p.65, October 01-01, 2002
• 3: Bischof, C., Lang, B., and Vehreschild, A. 2003. Automatic differentiation for MATLAB programs. In Proceedings in Applied Mathematics and Mechanics 2, 1 John Wiley, 50--53.
• 4: Christian Bischof , Peyvand Khademi , Andrew Mauer , Alan Carle, Adifor 2.0: Automatic Differentiation of Fortran 77 Programs, IEEE Computational Science & Engineering, v.3 n.3, p.18-32, September 1996 [doi>10.1109/99.537089]
• 5: Bischof, C. H., Khademi, P. M., Bouaricha, A., and Carle, A. 1996. Efficient computations of gradients and Jacobians by dynamic exploitation of sparsity in automatic differentiation. Optimiz. Meth. Softw. 7, 1--39.
• 6: C. H. Bischof , L. Roh , A. J. Mauer-Oats, ADIC: an extensible automatic differentiation tool for ANSI-C, Software—Practice & Experience, v.27 n.12, p.1427-1456, Dec. 1997 [doi>10.1002/(SICI)1097-024X(199712)27:12<1427::AID-SPE138>3.3.CO;2-H]
• 7: Jeff Borggaard , Arun Verma, On Efficient Solutions to the Continuous Sensitivity Equation Using Automatic Differentiation, SIAM Journal on Scientific Computing, v.22 n.1, p.39-62, 2000 [doi>10.1137/S1064827599352136]
• 8: Bradshaw, D. 2004. The use of numerical optimisation to determine on-limit handling behaviour of race cars. Ph.D. thesis, School of Engineering, Department of Automotive, Mechanical and Structural Engineering, Cranfield University, Bedfordshire, UK.
• 9: Coleman, T. F. and Verma, A. 1996. Structure and efficient Jacobian calculation. In Computational Differentiation: Techniques, Applications, and Tools, M. Berz, C. Bischof, G. Corliss, and A. Griewank, Eds. SIAM, Philadelphia, PA, 149--159.
• 10: Thomas F. Coleman , Arun Verma, ADMIT-1 : Automatic Differentiation and MATLAB Interface Toolbox, Cornell University, Ithaca, NY, 1998
• 11: Thomas F. Coleman , Arun Verma, The Efficient Computation of Sparse Jacobian Matrices Using Automatic Differentiation, SIAM Journal on Scientific Computing, v.19 n.4, p.1210-1233, July 1998 [doi>10.1137/S1064827595295349]
• 12: Thomas F. Coleman , Arun Verma, ADMIT-1: automatic differentiation and MATLAB interface toolbox, ACM Transactions on Mathematical Software (TOMS), v.26 n.1, p.150-175, March 2000 [doi>10.1145/347837.347879]
• 13: George Corliss , Christèle Faure , Andreas Griewank , Lauren Hascoët , Uwe Naumann, Automatic differentiation of algorithms: from simulation to optimization, Springer-Verlag New York, Inc., New York, NY, 2000
• 14: FastOpt 2003. Transformation of Algorithms in Fortran, Manual, Draft Version, TAF Version 1.6. FastOpt. http://www.FastOpt.com/taf.
• 15: Forth, S. A. 2001. User guide for MAD---a Matlab automatic differentiation toolbox. Applied Mathematics and Operational Research Report AMOR 2001/5 (June) Cranfield University (RMCS Shrivenham), Swindon, UK.
• 16: Forth, S. A. and Edvall, M. M. 2004. User Guide for MAD - MATLAB Automatic Differentiation Toolbox TOMLAB/MAD, Version 1.1 The Forward Mode. TOMLAB Optimization Inc., San Diego, CA. http://tomlab.biz/products/mad.
• 17: Forth, S. A. and Ketzscher, R. 2004. High-level interfaces for the MAD (Matlab Automatic Differentiation) package. In 4th European Congress on Computational Methods in Applied Sciences and Engineering (ECCOMAS), P. Neittaanmäki, T. Rossi, S. Korotov, E. Oñate, J. Périaux, and D. Knörzer, Eds. Vol. 2. University of Jyväskylä, Department of Mathematical Information Technology, Finland.
• 18: Shaun A. Forth , Mohamed Tadjouddine , John D. Pryce , John K. Reid, Jacobian code generated by source transformation and vertex elimination can be as efficient as hand-coding, ACM Transactions on Mathematical Software (TOMS), v.30 n.3, p.266-299, September 2004 [doi>10.1145/1024074.1024076]
• 19: John R. Gilbert , Cleve Moler , Robert Schreiber, Sparse matrices in matlab: design and implementation, SIAM Journal on Matrix Analysis and Applications, v.13 n.1, p.333-356, Jan. 1992 [doi>10.1137/0613024]
• 20: Andreas Griewank, Evaluating derivatives: principles and techniques of algorithmic differentiation, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 21: Andreas Griewank , David Juedes , Jean Utke, Algorithm 755: ADOL-C: a package for the automatic differentiation of algorithms written in C/C++, ACM Transactions on Mathematical Software (TOMS), v.22 n.2, p.131-167, June 1996 [doi>10.1145/229473.229474]
• 22: Griewank, A. and Reese, S. 1991. On the calculation of Jacobian matrices by the Markowitz rule. In Automatic Differentiation of Algorithms: Theory, Implementation, and Application, A. Griewank and G. F. Corliss, Eds. SIAM, Philadelphia, PA, 126--135.
• 23: Hairer, E. and Wanner, G. 1991. Ordinary Differential Equations II, Stiff and Differential-Algebraic Problems. Springer-Verlag, Berlin, Germany.
• 24: Holmström, K. and Edvall, M. M. January 2004. Chapter 19: The TOMLAB optimization environment. In Modeling Languages in Mathematical Optimization, J. Kallrath, Ed. APPLIED OPTIMIZATION 88. Kluwer Academic Publishers, Boston, MA.
• 25: Holmström, K., Göran, A. O., and Edvall, M. M. 2004. User's guide for TOMLAB 4.3. TOMLAB Optimization Inc., San Diego, CA. http://www.tomlab.biz.
• 26: Kharche, R. V. 2004. Source transformation for automatic differentiation in MATLAB. M.S. thesis, Cranfield University (Shrivenham Campus), Applied Mathematics & Operational Research Group, Engineering Systems Department (RMCS Shrivenham), Swindon, UK.
• 27: Naumann, U. 1999. Efficient calculation of Jacobian matrices by optimized application of the chain rule to computational graphs. Ph.D. thesis, Technical University of Dresden.
• 28: Uwe Naumann, Optimal accumulation of Jacobian matrices by elimination methods on the dual computational graph, Mathematical Programming: Series A and B, v.99 n.3, p.399-421, April 2004 [doi>10.1007/s10107-003-0456-9]
• 29: Nocedal, J. and Wright, S. J. 1999. Numerical Optimization. Operational Research Series. Springer-Verlag, New York, NY.
• 30: Pryce, J. D. and Reid, J. K. 1998. ADO1, a Fortran 90 code for automatic differentiation. Tech. Rep. RAL-TR-1998-057, Rutherford Appleton Laboratory, Chilton, UK. ftp://matisa.cc.rl.ac.uk/ pub/reports/prRAL98057.ps.gz.
• 31: Lawrence C. Rich , David R. Hill, Automatic differentiation in MATLAB, Applied Numerical Mathematics, v.9 n.1, p.33-43, Jan. 1992 [doi>10.1016/0168-9274(92)90065-L]
• 32: Ringrose, T. J. and Forth, S. A. 2002. Improved fitting of constrained multivariate regression models using automatic differentiation. In Proceedings in Computational Statistics, 15th Symposium (COMPSTAT'02), W. Hardle and B. Ronz, Eds. Physica-Verlag, Berlin, Germany, 383--388.
• 33: Ringrose, T. J. and Forth, S. A. 2005. Simplifying multivariate second order response surfaces by fitting constrained models using automatic differentiation. Technometrics 47, 3, 249--259.
• 34: Lawrence F. Shampine , Mark W. Reichelt, The MATLAB ODE Suite; , SIAM Journal on Scientific Computing, v.18 n.1, p.1-22, January. 1997 [doi>10.1137/S1064827594276424]
• 35: L. F. Shampine , Robert Ketzscher , Shaun A. Forth, Using AD to solve BVPs in MATLAB, ACM Transactions on Mathematical Software (TOMS), v.31 n.1, p.79-94, March 2005 [doi>10.1145/1055531.1055535]
• 36: Mohamed Tadjouddine , Shaun A. Forth , John D. Pryce, AD tools and prospects for optimal AD in CFD flux Jacobian calculations, Automatic differentiation of algorithms: from simulation to optimization, Springer-Verlag New York, Inc., New York, NY, 2000
• 37: Tapenade 2003. The TAPENADE tutorial. http://www-sop.inria.fr/tropics/tapenade/ tutorial.html.
• 38: The MathWorks Inc. 2003. Using Matlab, Version 6. The MathWorks Inc., MA.
• 39: The Mathworks Inc. Sept 2003. Optimization Toolbox User's Guide, Version 2. The Mathworks Inc., Natick MA.
• 40: Vehreschild, A. 2001. Semantic augmentation of MATLAB programs to compute derivatives. Diploma Thesis, Institute for Scientific Computing, Aachen University, Germany.
• 41: Verma, A. 1998a. ADMAT: Automatic differentiation in MATLAB using object oriented methods. In SIAM Interdisciplinary Workshop on Object Oriented Methods for Interoperability. SIAM, National Science Foundation, Yorktown Heights, New York, 174--183.
• 42: Arun Verma , Thomas F. Coleman, Structured automatic differentiation, 1998

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.5 Object-oriented Programming

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.4 Quadrature and Numerical Differentiation
          Subjects: Automatic differentiation
      G.1.5 Roots of Nonlinear Equations
          Subjects: Systems of equations
      G.1.6 Optimization
          Subjects: Gradient methods
      G.1.7 Ordinary Differential Equations
          Subjects: Stiff equations
  G.4 MATHEMATICAL SOFTWARE
      Subjects: Efficiency

General Terms:
Performance

Keywords:
MATLAB, efficient computation of Jacobians