Preconditioned all-at-once methods for large, sparse parameter estimation problems

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. Alternatively, in this paper we apply a preconditioned Krylov method directly to the KKT system arising from a Newton-type method for the constrained formulation (an 'all-at-once' approach). A variant of symmetric QMR is employed, and an effective preconditioner is obtained by solving the reduced Hessian system approximately. Since the reduced Hessian system presents significant expense already in forming a matrix-vector product, the savings in doing so only approximately are substantial. The resulting preconditioner may be viewed as an incomplete block-LU decomposition, and we obtain conditions guaranteeing bounds for the condition number of the preconditioned matrix. Numerical experiments are performed for the dc-resistivity and the magnetostatic problems in 3D, comparing the two approaches for solving the linear system at each Gauss-Newton iteration. 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.