The efficient computation of structured gradients using automatic differentiation

The advent of robust automatic differentiation tools is an exciting and imp ortant development in scientific computing. It is particularly noteworthy t hat the gradient of a scalar-valued function of many variables can be compu ted with essentially the same time complexity as required to evaluate the f unction itself. This is true, in theory, when the "reverse mode" of automat ic differentiation is used (whereas the "forward mode" introduces an additi onal factor corresponding to the problem dimension). However, in practice, performance on large problems can be significantly (and unacceptably) worse than predicted. In this paper we illustrate that when natural structure is exploited, fast gradient computation can be recovered, even for large dime nsional problems.