Acoustic inverse scattering via Helmholtz operator factorization and optimization

We present a joint acoustic/seismic inverse scattering and finite-frequency (reflection) tomography program, formulated as a coupled set of optimization problems, in terms of inhomogeneous Helmholtz equations. We use a higher order finite difference scheme for these Helmholtz equations to guarantee sufficient accuracy. We adapt a structured approximate   direct solver for the relevant systems of algebraic equations, which addresses storage requirements through compression, to yield a complexity for computing the gradients or images in the optimization problems that consists of two parts, viz., the cost for all the matrix factorizations which is roughly O(rN)O(rN) (for example O(rNlogN)O(rNlogN) when d = 2) times the number of frequencies, and the cost for all solutions by substitution which is roughly O(N)O(N) (for example O(Nlog(rlogN))O(Nlog(rlogN)) when d = 2) times the number of frequencies times the number of sources (events), where N = nd if n is the number of grid samples in any direction, and r is a parameter depending on the preset accuracy and the problem at hand. With this complexity, the multi-frequency approach to inverse scattering and finite-frequency tomography becomes computationally feasible with large data sets, in dimensions d = 2 and 3.