Efficient calculation of Jacobian and adjoint vector products in the wave propagational inverse problem using automatic differentiation

Wave propagational inverse problems arise in several applications including medical imaging and geophysical exploration. In these problems, one is int erested in obtaining the parameters describing the medium from its response to excitations. The problems are characterized by their large size, and by the hyperbolic equation which models the physical phenomena. The inverse p roblems are often posed as a nonlinear data-fitting where the unknown param eters are found by minimizing the misfit between the predicted data and the actual data. In order to solve the problem numerically using a gradient-ty pe approach, one must calculate the action of the Jacobian and its adjoint on a given vector. In this paper, we explore the use of automatic different iation (AD) to develop codes that perform these calculations. We show that by exploiting structure at 2 scales. we can arrive at a very efficient code whose main components are produced by AD. In the first scale we exploite t he time-stepping nature of the hyperbolic solver by using the "Extended Jac obian" framework. In the second (finer) scale, we exploit the finite differ ence stencil in order to make explicit use of the sparsity in the dependenc e of the output variables to the input variables. The main ideas in this wo rk are illustrated with a simpler, one-dimensional version of the problem. Numerical results are given for both one- and two- dimensional problems. We present computational templates that can be used in conjunction with optim ization packages to solve the inverse problem. (C) 2000 Academic Press.