Multigrid all-at-once methods for large
scale inverse problems

E. Haber, U. Ascher

Dept of Computer Science UBC, Vancouver BC, Canada

Abstract

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 obtained.
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. .