Memory/Speed Tradeoffs in Implementations of Chain Rules for Automatic Differentiation
by
Igor Tsukanov
University of Wisconsin-Madison, U.S.A.
Coauthors: Michael Hall (University of Wisconsin-Madison, U.S.A.)

The main contribution of this paper is the development of a data structure and algorithms to compute the partial derivatives of functions comprised of elementary functions and binary operators. The differentiation of all operators and transcendental functions is performed via recursively defined chain rules that propagate derivatives from the lowest to the highest order. Using these chain rules, we can calculate partial derivatives exactly without any restrictions on the order of the derivatives or the number of independent variables.

We have implemented AD with a tuple class which contains a specialized data structure: a differential tuple that holds values of partial derivatives, binomial coefficients, and index arrays.

We discuss two implementations of the tuple class optimized (1) for low memory storage and (2) for high speed computations. The first implementation stores only arrays of derivatives and binomial coefficients; every time a partial derivative is computed, binomial coefficients must be multiplied, and the positions of partial derivatives must be found. The second implementation eliminates these steps by using an additional data structure to allow constant time access to precomputed products of binomial coefficients and the positions of partial derivatives.

In terms of the number of independent variables and maximum order of derivatives, we estimate the time complexity of the proposed algorithms and the size of the data structure.

Memory/Speed Tradeoffs in Implementations of Chain Rules for Automatic Differentiation

Date received: December 28, 1999