9. Going beyond Forward and Reverse
Society for Industrial and Applied Mathematics eBooks · 2008
So far we have considered two ways of calculating the Jacobian entries ∂yi/∂xj from the elemental partials cij = ∂φi/∂υj, namely, the forward and reverse modes. In both cases only multiplications and additions of floating point numbers are needed once the elemental partials cij have been evaluated at the current argument x ∈ ℝn. From now on we will refer to this process as derivative accumulation. As will be shown in this chapter, the “global” partials ∂yi/∂xj can be accumulated from the “local” partials cij in very many different ways. The forward and reverse modes turn out to be “pure” choices in a huge variety of strategies for accumulating derivatives by eliminating edges or vertices on the linearized computational graph. The natural goal of accumulating Jacobians with a minimal number of arithmetic operations is on larger problems elusive because it has been proven by Naumann [Nau06] to be NP-hard, as will be discussed in section 9.5. Nevertheless, the freedom to apply the chain rule in varying orders opens up avenues for various preaccumulations, for example, the statement-level reverse mode employed by the tangent mode of ADIFOR or the dirty-vector propagation suggested by Christianson, Dixon, and Brown [CDB96]. Another benefit is that the complexity of Jacobian calculations seems to become a little bit less dependent on the particular way in which the underlying function has been written down. Finally, the associativity of the chain rule can also be used to perform accumulation in parallel on independent sections of the graph, thus introducing concurrency along the (evaluation) “time-axis,” which is typically not present in the underlying forward simulation.