Fast Krylov subspace methods for solving large-scale inverse problems

Inverse problems are part of a mathematical framework used to estimate parameters that characterize a physical system but are difficult to measure directly. An example application is hydraulic tomography which is a method of imaging the susurface. Water is pumped at designated pumping wells and the measured pressure response is recorded at corresponding observation wells. Inverse problems of this type are particularly challenging both mathematically as they are ill-posed, and computationally, as they generally require repeated solutions of large-scale partial differential equations. For the class of inverse problems that we describe, solving shifted systems of linear equations is a major computational bottleneck.

We have developed two iterative algorithms for solving these ill-conditioned shifted linear systems. Krylov subspace methods are particularly appealing because of their shift-invariant property. By exploiting this property, only a single Krylov basis is computed and the solution for multiple shifts can be obtained at a cost that is nearly equal to the cost of solving a single system. We then show how the time and frequency dependent inverse problems can be accelerated using these Krylov subspace solvers. The resulting computational gains will be demonstrated on synthetic model problems from oscillatory and transient hydraulic tomography.