You are here

Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation

Andreas Griewank
Publisher: 
SIAM
Publication Date: 
2000
Number of Pages: 
390
Format: 
Paperback
Series: 
Frontiers in Applied Mathematics 19
Price: 
64.50
ISBN: 
978-0898714517
Category: 
General
[Reviewed by
Dan Kalman
, on
03/3/2001
]

A computer programmer is working on a simulation of a satellite communications system. The program already contains a function for the position and velocity of the satellite at any time. Similarly, there is a function for the position and velocity of a tracking station on the ground. Now the programmer wants to model the motion of a tracking station radio antenna as it turns to follow the progress of the satellite. The angles governing antenna orientation are easily computed using standard mathematical operations. But the angular speeds are much more complicated. Fortunately, the programmer is using a computer language in which derivatives are computed automatically without any special programming. The framework that makes this possible is called automatic differentiation or algorithmic differentiation.

To define the situation more clearly, the simulation already includes a programmer defined function, sat(t), which returns a numerical vector (x,y,z,x',y',z') consisting of the satellite position r=(x,y,z) and velocity v = (x',y',z') at any specified time t. It is important in what follows to note that r and v are not given by symbolic expressions. Indeed, high fidelity motion models generally involve iterative procedures for integrating differential equations. Similarly, there is a function trak(t) which returns a numerical vector (a,b,c,a',b',c') where p = (a,b,c) is the position and p' = (a',b',c') is the velocity of the tracking station at time t. The radio antenna follows the satellite by swiveling on two axes. The first is fixed in a vertical position, and the antenna can rotate through 360 degrees. The second is perpendicular to the first, and rotates with the antenna. Together these axes are similar to the arrangement on an office swivel chair. To point at a particular point in the sky, you swivel the chair about its vertical axis to the right compass heading, and then tilt back until your line of sight points in the direction of the satellite.

Consider a fixed time t. We have r and p from the sat and trak functions. Assume a spherical earth centered at the origin, with north pole on the positive z axis, and let k = (0,0,1). Then the swivel and tilt angles for the antenna can be determined as follows:

u = p/|p|

a unit vector pointing up from the station

e = k x u / |k x u|

a unit vector point east from the station

n = u x e

a unit vector point north from the station

L = r - p

the vector from the station to the satellite

Le = L. e

component of L parallel to e

Ln = L. n

component of L parallel to n

Lu = L. u

component of L parallel to u

swivel = arctan(Le/Ln)

 

tilt = arcsin(Lu/|L|)

 

The derivatives of swivel and tilt are a little more trouble. Using symbolic differentiation quickly leads to unmanageable expressions. Indeed, the entire point of this example is to illustrate how relatively simple equations for calculating a function can easily lead to much more complicated equations for derivatives.

Automatic differentiation would provide the derivatives of swivel and tilt with no explicit coding by the programmer. The results have the same accuracy you would expect for the functions sat and trak, and are obtained neither by approximating derivatives numerically using difference quotients, nor by symbolic computer algebra. Instead, the computing system propagates the correct numerical values of the derivatives in the course of carrying out arithmetic operations and evaluating library functions (like exponentials and trig functions). Here is a very simple example. Suppose we have already calculated numerical values for f, f', g, and g' at t = 1. These values have been assigned to variables f, g, df, dg, in the computer program. Next we wish to calculate the value of fg and the derivative (fg)'. We put a line of code in the program: p = f*g. The computer system includes also the line dp = f*dg+g*df Then, although we have not explicitly inserted code for the derivative of fg, it is computed, and computed with full accuracy. That is the spirit of algorithmic differentiation.

So much has been understood for a long time. Indeed, for quite readable presentations of the basic ideas of algorithmic differentiation, references [1] and [2] are still a good starting point. But in the last two decades there has been a good deal of work extending the basic ideas of automatic differentiation to sophisticated computational tools. Along the way, workers in the field have investigated standard issues in numerical analysis, including convergence properties of iterative procedures, error analysis, and computational complexity. They have also found a range of significant applications far beyond the simple satellite example discussed above.

In Evaluating Derivatives: Principles and Techniques of Algorithmic Differentiation, Andreas Griewank provides a comprehensive and organized account of algorithmic differentiation. This is a book intended for users and creators of numerical software, as well as those interested in theoretical aspects of numerical analysis. It serves its intended audiences very well. The writing is charming and urbane, and the development quite abstract and elegant. It also provides an exhaustive list of references and pointers to related work. If you want to get a better understanding of how automatic differentiation can be applied in sophisticated scientific computing, or of the theoretical questions that arise in this area, then this is the book for you.

The book is published by SIAM. See their webpage for the book for a more detailed description of the contents.


References:

[1] Richard D. Neidinger. Automatic differentiation and APL.College Mathematics Journal, 20(3): 238 - 251, May 1989.

[2] Louis B. Rall, The arithmetic of differentiation.Mathematics Magazine, 59(5): 275 - 282, December 1986.


Dan Kalman (kalman@american.edu) is associate professor of mathematics at American University, Washington, DC. He became interested in algorithmic differentiation while working in the aerospace industry in the 1980's.

Preface; Prologue; Introduction; Part I: Tangents and Gradients. A Framework for Evaluating Functions; Fundamentals of Forward and Reverse; Repeating and Extending Reverse; Implementation and Software; Part II: Jacobians and Hessians. Sparse Forward and Reverse; Exploiting Sparsity by Compression; Going Beyond Forward and Reverse; Observations on Efficiency; Part III: Advances and Reversals. Taylor and Tensor Coefficients; Differentiation without Differentiability; Serial and Parallel Reversal Schedules; Bibliography; Index.