Scalable Newton-Krylov Methods for Inverse Wave Propagation

Friday, April 26, 2002 - 3:00pm - 4:00pm
Keller 3-180
Omar Ghattas (Carnegie-Mellon University)
Our ultimate goal is to determine mechanical properties of large sedimentary basins (such as the greater Los Angeles Basin) from seismograms of past earthquakes, using elastic wave propagation to model the forward problem. Our current forward simulations involve 100 million finite elements; over the next several years the desired increase in resolution and growth in basin size will require at least an order of magnitude increase in number of unknowns. Inversion of such forward models provides a major challenge for inverse methods. It is imperative that these methods be able to scale to O(10^9) state variables, to highly-resolved (perhaps grid-based) elastic material models of large seismic basins, and to parallel architectures with thousands of processors.

In this talk we consider prototype parallel algorithms for inverting synthetic scalar wave propagation data for grid-parameterized velocity models. Tikhonov and Total Variation regularization treat ill-posedness associated with rough components of the velocity model, while grid/frequency continuation addresses multiple minima associated with smooth components. We have developed and implemented inexact parallel (Gauss)-Newton-Krylov methods for the solution of the inverse problem. These make use of inexactly-terminated conjugate gradient (CG) solution of (Gauss)-Newton linearizations of the reduced gradient equation. CG matrix-vector products are computed via checkpointed adjoints, which involve forward and adjoint wave equation solutions at each iteration. Preconditioning is via limited memory BFGS updates, initialized with approximate inverses of an approximation to the Gauss-Newton Hessian.

Experience on moderately-sized problems (tens to hundreds of thousands of grid points) suggests mesh-independence of Newton iterations, near-mesh independence of CG iterations, and good parallel efficiency. The results also demonstrate significant speedups over LM-BFGS as the solver. We are currently running large inversions on the new 6 teraflop/s TCS at the Pittsburgh Supercomputing Center, and hope to be able to present scalability studies on up to 512^3 grids and 2048 processors at the workshop.

This work is joint with Volkan Akcelik (Carnegie Mellon University) and George Biros (Courant Institute), and is part of the Quake Project ( at Carnegie Mellon, San Diego State, and UC Berkeley.