Adjoint Broyden a la GMRES

Andreas Griewank ( griewankmathematik.hu-berlin.de)
Sebastian Schlenkrich (Sebastian.Schlenkrich2mailbox.tu-dresden.de)
Andrea.Walther@tu-dresden.de Walther (Andrea.Walthertu-dresden.de)

Abstract: It is shown that a compact storage implementation of a quasi-Newton method based on the adjoint Broyden update reduces in the affine case exactly to the well established GMRES procedure. Generally, storage and linear algebra effort per step are small multiples of n k, where n is the number of variables and k the number of steps taken in the current cycle. In the affine case the storage is exactly (n+k) k and in the nonlinear case the same bound can be achieved if adjoints, i.e. transposed Jacobian-vector products are available. A transposed-free variant that relies exclusively on Jacobian-vector products (or possibly their approximation by divided differences) requires roughly twice the storage and turns out to be somewhat slower in our numerical experiments reported at the end.

Keywords: nonlinear equations, quasi-Newton methods, adjoint based update, compact storage, generalized minimal residual, Arnoldi process, automatic differentiation

Category 1: Nonlinear Optimization (Nonlinear Systems and Least-Squares )

Citation: Matheon-Berlin Preprint 413

Download: [PDF]

Entry Submitted: 10/29/2007
Entry Accepted: 10/29/2007
Entry Last Modified: 10/29/2007

Modify/Update this entry