Multiple vector-Jacobian products are cheap (Q1294605)

The authors consider the evaluation of several quantities which may be derived from a differentiable map \(F:D\subset {\mathbb{R}}^n\to {\mathbb{R}}^m\) with \(m\geq n\), such as the residual at a point \(x\), \(F(x)\), or Jacobian-vector products \(F(x)S \in {\mathbb{R}}^{m\times p}\), or vector-Jacobian products \(U^TF(x)\in {\mathbb{R}}^{q\times n}\). The evaluation of \(F(x)\) is viewed as resulting from a sequence of simpler transformations \(z_i=\Phi_i(z_{i-1})\) with \(\Phi_i:Z\to Z\) for \(i=1,\dots,l\) where \(Z:={\mathbb{R}}^r\) is some common state space. With \(z_0=P^Tx\) for some projection \(P\in {\mathbb{R}}^{n\times r}\), and \(Q\in {\mathbb{R}}^{m\times r}\) a projection of the final state \(z_l\), there follows the identity \(y=F(x)=Q\Phi_l(\Phi_{l-1}(\cdots(\Phi_1(P^Tx)\cdots)))\). Now by premultiplying \(F'(x)\) by \(\dot x\) or postmultplying \(F'(x)^T\) by \(\overline y\), one has \[ \dot y= F'(x)\dot x= Q[\Phi'_l(z_{l-1})[\Phi'_{l-1}(z_{l-2})[\cdots[\Phi'_1(z_0)(P^T \dot x)]]]\cdots]]] \] and \[ \overline x=F'(x)^T\overline y=P[\Phi'_1(z_0)^T[\Phi'_2(z_1)^T[\cdots [\Phi'_l(z_{l-1})(Q^T\overline y)]]]\cdots]]], \] respectively. In both equations the square brackets indicate the order of execution in the forward and reverse order of computational differentiation, respectively. Assuming that the ingredients for calculating the former product have been stored, also the latter product can be calculated at essentially the same expense. It is suggested that computing, e.g., Jacobian-vector and Hessian-vector products as a bundle gives an efficient way to compute derivative information. Several numerical examples are presented.