Andreas Griewank
Frontiers in Applied Mathematics 19
Algorithmic, or automatic, differentiation (AD) is concerned with the accurate and efficient evaluation of derivatives for functions defined by computer programs. No truncation errors are incurred, and the resulting numerical derivative values can be used for all scientific computations that are based on linear, quadratic, or even higher order approximations to nonlinear scalar or vector functions. In particular, AD has been applied to optimization, parameter identification, equation solving, the numerical integration of differential equations, and combinations thereof. Apart from quantifying sensitivities numerically, AD techniques can also provide structural information, e.g., sparsity pattern and generic rank of Jacobian matrices.
This first comprehensive treatment of AD describes all chainrule-based techniques for evaluating derivatives of composite functions with particular emphasis on the reverse, or adjoint, mode. The corresponding complexity analysis shows that gradients are always relatively cheap, while the cost of evaluating Jacobian and Hessian matrices is found to be strongly dependent on problem structure and its efficient exploitation. Attempts to minimize operations count and/or memory requirement lead to hard combinatorial optimization problems in the case of Jacobians and a well-defined trade-off curve between spatial and temporal complexity for gradient evaluations.
The book is divided into three parts: a stand-alone introduction to the fundamentals of AD and its software, a thorough treatment of methods for sparse problems, and final chapters on higher derivatives, nonsmooth problems, and program reversal schedules. Each of the chapters concludes with examples and exercises suitable for students with a basic understanding of differential calculus, procedural programming, and numerical linear algebra.
Audience
This volume will be valuable for designers and users of algorithms and software for nonlinear computational problems. It opens up an exciting opportunity to develop new algorithms that reflect the availability of accurate derivatives and their true cost to achieve improvements in speed and reliability. Some familiarity with modern approaches to the seemingly straightforward task of evaluating derivatives will benefit any mathematician, scientist or engineer.
Contents
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.
2000 / xxiv + 369 pages / Softcover / ISBN-13: 978-0-898714-51-7 / ISBN-10: 0-89871-451-6 /
List Price $64.50 / SIAM Member Price $45.15 / Order Code FR19
|
