Bibliographic record for `Naumann:2008:OVE'

@Article{Naumann:2008:OVE,
  author =       "Uwe Naumann and Yuxiao Hu",
  title =        "Optimal Vertex Elimination in Single-Expression-Use Graphs",
  volume =       "35",
  number =       "1",
  journal =      "{ACM} Transactions on Mathematical Software",
  month =        jul,
  year =         "2008",
  pages =        "2",
  note =         "Article 2, 20 pages",
  URL =          "http://doi.acm.org/10.1145/1377603.1377605",
  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 paper 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.
                 \par 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 paper 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.",
}