Adjoint Broyden a la GMRES
Please always quote using this URN:urn:nbn:de:0296-matheon-4243
- It is shown here 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\cdot 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)\cdot 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.
Author: | Andreas Griewank, Sebastian Schlenkrich, Andrea Walther |
---|---|
URN: | urn:nbn:de:0296-matheon-4243 |
Referee: | Peter Deuflhard |
Document Type: | Preprint, Research Center Matheon |
Language: | English |
Date of first Publication: | 2007/10/25 |
Release Date: | 2007/10/24 |
Institute: | Humboldt-Universität zu Berlin |
Preprint Number: | 413 |