Vertex elimination for algorithmic piecewise differentiation.

Abstract

A piecewise affine approximation of a mathematical function can be represented in abs-normal form. Given a computer program implementing a function, this representation can be efficiently evaluated by algorithmic piecewise differentiation. By successively eliminating switching variables from such a representation, this article introduces the concept of reduced models. The novel contribution of this article is to describe the underlying phenomena by introducing a directed acyclic graph called the condensed computational graph with corresponding vertex elimination sequences. This graph-theoretical approach allows the formulation of novel combinatorial optimization problems. For these problems, new combinations of three quantitative measures are proposed: minimizing the number of floating-point operations, minimizing the length of the longest path, and minimizing the fill-in of a vertex elimination sequence. This goal-oriented approach paves the way not only for the design of certain properties of reduced models but also for the development of efficient graph-theoretical strategies for their construction.