Computational Science and Engineering

College of Computing

Georgia Institute of Technology

266 Ferst Drive

Atlanta GA 30332-0765

### Full Waveform Acoustic and Elastic Reconstructions with Multiple Sources

We consider the inverse medium problem for the time-harmonic
wave equation with broadband and multi-point illumination in the low
frequency regime. Such a problem finds many applications in
geosciences (e.g. ground penetrating radar), non-destructive
evaluation (acoustics), and medicine (optical tomography). We use an
integral-equation (Lippmann-Schwinger) formulation, which we
discretize using a quadrature method. We consider only small
perturbations (Born approximation). To solve this inverse problem, we
use a least-squares formulation. We present a new fast algorithm for
the efficient solution of this particular least-squares problem.
If *N*_{fr} is the number of excitation frequencies, *N_*_{s} the
number of different source locations for the point illuminations,
*N*_{d} the number of detectors, and *N* the parametrization for the
scatterer, a dense singular value decomposition for the overall
input-output map will have
* [min(N*_{s} N_{fr} N_{d}, N)]^{2}
x max(N_{s} N_{fr}N_{d}, N) cost. We have developed a fast
SVD-based preconditioner that brings the cost down to
*O( N*_{s} N_{fr} N_{d} N)
thus, providing orders of magnitude improvements over a black-box
dense SVD and an unpreconditioned linear iterative solver.

Joint work with Stephanie Chaillat, Computational Science and Engineering, Georgia Institute of Technology.

Systems Engineering & Operations Research Department

George Mason University

Mailstop 4A6

Fairfax, VA 22030

### Convergence and Descent Properties for a Class of Multilevel Optimization Algorithms

I present a multilevel optimization approach (called MG/Opt) for the solution of constrained optimization problems. The approach assumes that one has a hierarchy of models, ordered from fine to coarse, of an underlying optimization problem, and that one is interested in finding solutions at the finest level of detail. In this hierarchy of models, calculations on coarser levels are less expensive, but also are of less fidelity, than calculations on finer levels. The intent of MG/Opt is to use calculations on coarser levels to accelerate the progress of the optimization on the finest level.
Global convergence (i.e., convergence to a Karush-Kuhn-Tucker point from an arbitrary starting point) is ensured by requiring a single step of a convergent method on the finest level, plus a line-search (or other globalization technique) for incorporating the coarse level corrections. The convergence results apply to a broad class of algorithms with minimal assumptions about the properties of the coarse models.

I also analyze the descent properties of the algorithm, i.e., whether the coarse level correction is guaranteed to result in improvement of the fine level solution. Although additional assumptions are required in order to guarantee improvement, the assumptions required are likely to be satisfied by a broad range of optimization problems.

Aerospace Computational Design Laboratory

Massachusetts Institute of Technology

Bldg 33 Rm 408

77 Massachusetts Avenue

Cambridge, MA 02139

### Variance Reduction in Computational Risk Assessment using Reduced Order Models

Computational risk assessment uses mathematical models and
computational methods to estimate the probability of failure in an
engineering system, given uncertainty in the inputs, operating
condition, and other factors. When the probability of such events is
small, traditional Monte Carlo method requires evaluation of the
mathematical model on a very large number of random samples. When the
model is computationally expensive to evaluate, accurate risk
assessment is often computationally infeasible without methods of
reducing the number of required samples.
We present several methods for reducing the variance of Monte Carlo
method, thus the number of required samples, by using reduced order
models of computationally intensive models. These methods combine
reduced order models with methods widely used in statistics, including
control variates, importance sampling and stratified sampling. We
demonstrate these techniques in engineering risk assessment problems
involving unsteady hydrodynamics and hypersonic air breathing engines.
We show that our methods reduce the computation cost by an order of
magnitude, yet computes unbiased estimate of the probabilities of
failure.