Optimal vertex elimination in single-expression-use graphs

ABSTRACT

The source transformation tool for automatic differentiation of Fortran programs ADIFOR uses a preaccumulation technique to speed up tangent-linear codes significantly compared to the standard forward mode. Reverse mode automatic differentiation is applied to all scalar assignments to generate efficient code for the computation of local gradients. It has been well known for some time that reverse mode is not necessarily the optimal choice for the computation of these statement-level gradients as it does not minimize the number of operations required. This article presents an efficient algorithm for the solution of this combinatorial optimization problem. The corresponding software is freely available for downloading on our website. Developers of software for automatic differentiation are invited to integrate the algorithm into their tools.

Gradients of scalar multivariate functions can be computed by elimination methods on the linearized computational graph. The combinatorial optimization problem that aims to minimize the number of arithmetic operations performed by the elimination algorithm is known to be NP-complete. In this article we present a polynomial algorithm for solving a relevant subclass of this problem's instances. The proposed method relies on the ability to compute vertex covers in bipartite graphs in polynomial time. A simplified version of this graph algorithm is used in a research prototype of the differentiation-enabled NAGWare Fortran compiler for the preaccumulation of local gradients of scalar assignments in the context of automatic generation of efficient tangent-linear code for numerical programs.

REFERENCES

• 1: Baur, W. and Strassen, V. 1983. The complexity of partial derivatives. Theoret. Comput. Sci. 22, 317--330.
• 2: Berz, M., Bischof, C., Corliss, G., and Griewank, A., Eds. 1996. Computational Differentiation: Techniques, Applications, and Tools. Proceedings Series. SIAM.
• 3: 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]
• 4: Bischof, C. and Haghighat, M. 1996. Hierarchical approaches to automatic differentiation. In Computational Differentiation: Techniques, Applications, and Tools. Proceedings Series. SIAM. 82--94.
• 5: Martin Bücker , George Corliss , Paul Hovland , Uwe Naumann , Boyana Norris, Automatic Differentiation: Applications, Theory, and Implementations (Lecture Notes in Computational Science and Engineering), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 6: 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
• 7: Corliss, G. and Griewank, A., Eds. 1991. Automatic Differentiation: Theory, Implementation, and Application. Proceedings Series. SIAM.
• 8: Jack Edmonds , Richard M. Karp, Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems, Journal of the ACM (JACM), v.19 n.2, p.248-264, April 1972 [doi>10.1145/321694.321699]
• 9: Ford, L. and Fulkerson, D. 1962. Flows in Networks. Princeton University Press.
• 10: 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]
• 11: Ralf Giering , Thomas Kaminski, Recipes for adjoint code construction, ACM Transactions on Mathematical Software (TOMS), v.24 n.4, p.437-474, Dec. 1998 [doi>10.1145/293686.293695]
• 12: Andreas Griewank, Evaluating derivatives: principles and techniques of algorithmic differentiation, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2000
• 13: 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]
• 14: Griewank, A. and Reese, S. 1991. On the calculation of Jacobian matrices by the Markovitz rule. In Automatic Differentiation: Theory, Implementation, and Applications. Proceedings Series. SIAM. 126--135.
• 15: Griewank, A. and Vogel, O. 2003. Analysis and exploitation of Jacobian scarcity. In Proceedings of the International Conference on High Performance Scientific Computing (HPSC). Springer.
• 16: Harary, F. 1969. Graph Theory. Addison-Wesley.
• 17: Hopcroft, J. and Karp, R. 1973. An n^5/2 algorithm for physics graphs. SIAM J. Comput. 2, 225--231.
• 18: Gershon Kedem, Automatic Differentiation of Computer Programs, ACM Transactions on Mathematical Software (TOMS), v.6 n.2, p.150-165, June 1980 [doi>10.1145/355887.355890]
• 19: König, D. 1931. Graphs and matrices (Hungarian). Mat. Fiz. Lapok 38, 116--119.
• 20: Naumann, U. 1999. Efficient calculation of Jacobian matrices by optimized application of the chain rule to computational graphs. Ph.D. thesis, Technical University Dresden, Dresden, Germany.
• 21: 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]
• 22: Uwe Naumann, Optimal Jacobian accumulation is NP-complete, Mathematical Programming: Series A and B, v.112 n.2, p.427-441, November 2007 [doi>10.1007/s10107-006-0042-z]
• 23: Uwe Naumann , Jan Riehme, A differentiation-enabled Fortran 95 compiler, ACM Transactions on Mathematical Software (TOMS), v.31 n.4, p.458-474, December 2005 [doi>10.1145/1114268.1114270]
• 24: Naumann, U. and Riehme, J. 2006. Computing adjoints with the NAGWare Fortran 95 compiler. In Automatic Differentiation: Applications, Theory, and Tools. Lecture Notes on Computational Science and Engineering, vol. 50, Springer, Berlin, Germany.
• 25: Martin Bücker , George Corliss , Paul Hovland , Uwe Naumann , Boyana Norris, Automatic Differentiation: Applications, Theory, and Implementations (Lecture Notes in Computational Science and Engineering), Springer-Verlag New York, Inc., Secaucus, NJ, 2006

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.4 Quadrature and Numerical Differentiation
          Subjects: Automatic differentiation

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory

General Terms:
Algorithms

Keywords:
Vertex elimination, single-expression-use graph