A large part of my job for the last eight years has been dealing with the first- and second-order derivatives of financial instruments. Hence, I find myself intimately aware of the numerical inaccuracies and computation time complexity of finite difference techniques. Thus, it was with great anticipation that I started reading this book about a world of faster and more accurate derivatives.
Chapter 1 broadly describes a motivation for algorithmic differentiation. It starts off with a few examples where derivatives are required, such as a steepest descent search in nonlinear programming, how to use the Newton algorithm for solving systems of nonlinear equations, and how to deal with constraints. Having defined some problems, the author describes manual differentiation before moving on to approximation techniques. It is in the context of finite differences that the inaccuracies introduced by finite precision floating-point numbers are analyzed.
Chapter 2 introduces the tangent linear and adjoint models around which algorithmic differentiation is based. The tangent linear model computes the derivative of the output with respect to the input on a source code line-by-line basis, where the derivative is propagated along with the original computation. As such, this is also called the forward mode. The order of complexity for computing the derivative is proportional to the number of inputs. The adjoint model effectively computes the derivative of the input with respect to the output, and thus its time complexity scales in proportion to the number of outputs. In the many cases where there are significantly fewer outputs than inputs, the adjoint model provides sizable time savings. To achieve this, in the adjoint model, the code has to be inverted and the derivative computed going backwards through the code (reverse mode). Obviously, this is a much more onerous task, and so the chapter ends by describing how to achieve call tree reversal.
Chapter 3 covers higher-order derivatives. Given that we have two modes to differentiate a function, we obviously have four combinations of modes to compute the second derivatives: forward over forward, reverse over forward, forward over reverse, and reverse over reverse. The first still generates tangent linear code, while the remaining three stay as adjoint models. Each of these is dealt with in detail in this chapter, and supplemented with example source code to show what a simple function looks like after each of the four possible combinations of transformations has been applied to it. Although code transformation, or rather code generation of derivative code, is the primary focus of this book, both tangent linear and adjoint model computation can be performed by overriding operators on a custom defined data type. Hence, this chapter also defines data types required for computing first- and second-order derivatives, and how operator overriding can be used to achieve the computation of the derivative with minimal change to the original source code. Numerical timings of the various differentiation combinations on some sample toy problems are provided throughout.
I found chapter 4 to be the weakest in the book. The intention is to detail how one would build a derivative code compiler. However, to do so requires a whole book’s worth of knowledge on compiler design, not just half of a chapter. Hence, this chapter is a whirlwind of topics, including deterministic and nondeterministic finite automata; call flow graphs and parse trees; regular expressions and their conversion to state automata; syntax analysis; top-down and bottom-up parsers; left-right parsers and dealing with operator precedence; and attribute grammars. Luckily, the author sticks to a single lexical analyzer (flex) and a single parser (bison). Input files, data formats, and syntax are described for both flex and bison, and usage examples are provided.
The final chapter brings it all together. Using dcc version 0.9, the derivative code compiler written as a part of research efforts into algorithmic differentiation, the author walks the user through all the theoretical topics covered in chapters 2 and 3. Starting with how the compiler changes function signatures to include the additional input and output parameters that will contain the derivatives, Naumann then discusses how local variables are dealt with. The bulk of the chapter looks at three examples of increasing complexity. The first is the simple function y = sin (x). The second covers nested functions, to which the author adds the challenge of dealing with a function that modifies its input parameter. The final example is a function that takes a vector of doubles as input. For each of these examples, the author generates the two types of first-order derivative code (tangent linear and adjoint), as well as the four types of second-order derivative code described above.
The book ends with three appendices, the last of which contains hints for solutions to the numerous exercise problems at the end of each chapter.
Overall, I must admit I expected better. To me, this book feels like two books, one on algorithmic differentiation and the other on derivative code compilers, neither of which is truly complete.
