Multigrid all-at-once methods for large
scale inverse problems
E. Haber, U. Ascher
Dept of Computer Science UBC, Vancouver BC, Canada
The problem of recovering a parameter function based on
measurements of solutions of a system of partial differential
equations in several space variables leads to a number of
computational challenges. Upon discretization of a regularized
formulation a large, sparse constrained optimization problem is
Typically in the literature, the constraints are eliminated and the resulting unconstrained formulation is solved by some variant of Newton's method, usually the Gauss-Newton method. A preconditioned conjugate gradient algorithm is applied at each iteration for the resulting reduced Hessian system.
In this talk we apply instead a multigrid method directly to the KKT system arising from a Newton-type method for the constrained formulation (an ``all-at-once'' approach). Since the reduced Hessian system presents significant expense already in forming
a matrix-vector product, the savings are substantial.
Numerical experiments are performed for the DC-resistivity problem in 3D, comparing the two approaches for solving the linear system at each Gauss-Newton iteration and a substantial efficiency gain is demonstrated.
The relative efficiency of our proposed method is even higher in the context of inexact Newton-type methods, where the linear system at each iteration is solved less accurately. .