**TOPS Software for Optimization of Simulated Systems**

**PIs:** V. Akçelik^2^, S. Benson^1^, G. Biros^3^, X. Cai^5^, O.
Ghattas^2^, D. Keyes^4^, J. Moré^1^, T. Munson^1^, J. Sarich^1^, B.
Smith^1^, **Principal affiliates:** L. C. McInnes (CCTTSS), P. Hovland
(PERC)

^1^Argonne National Lab, ^2^Carnegie Mellon U., ^3^Columbia U., ^4^New
York U., ^5^U. Colorado-Boulder

Summary

***In support of known and anticipated application requirements for
parameter identification, design optimization, optimal control, and data
assimilation in complex systems, the Terascale Optimal PDE Simulations
(TOPS) project is creating optimization packages that leverage and
integrate its scalable solvers.***

One of the outstanding challenges of computational science is nonlinear
parameter estimation of partial differential equation (PDE) systems.
Such inverse problems are significantly more difficult to solve than the
associated forward problems, due to ill-posedness, large dense
ill-conditioned inversion operators, multiple minima, space-time
coupling, the possibility of discontinuous inversion fields, and the
need to solve the forward problem repeatedly. TOPS has developed a
nonlinear parameter estimation code for a large class of time-dependent
PDEs. This code is based on the parallel PDE solver software PETSc and
uses preconditioners from the PDE-constrained optimization library
Veltisto (which, in turn, is built from PETSc components).

Figure 1 illustrates the application of the parameter estimation code to
identifying the geologic structure of the Los Angeles Basin from surface
observations of past earthquakes. The inverse problem involves 17.2
million parameters and 70 billion total unknowns, and was solved in 24
hours on 2048 processors of an HP AlphaServer system. The underlying
parallel algorithm scales well: the number of outer and inner iterations
is insensitive to problem size. This work represents one of the largest
inversion problems ever solved, and won the 2003 Gordon Bell Prize for
Special Achievement.

![](media/image1.jpeg){width="2.363888888888889in"
height="1.604861111111111in"}

![](media/image2.jpeg){width="2.964583333333333in"
height="1.6888888888888889in"}

Figure 1. *Reconstruction of a portion of the LA Basin geology via
earthquake ground motion inversion, using the TOPS-developed parallel
multiscale Gauss-Newton-Krylov parameter estimation code. The top image
shows an isosurface from the target basin used to generate synthetic
surface seismograms. The bottom image shows the inverted basin
structure. Geological features larger than a quarter wavelength are
recovered by the inversion.*

The parameter estimation code integrates total variation regularization
(addressing the ill-posedness of high-frequency components and the
discontinuity of the inversion field), matrix-free Gauss-Newton-Krylov
iteration, algorithmic checkpointing (addressing the forward-backward
time coupling), multi-scale continuation (addressing multiple minima),
and an improved limited-memory preconditioner.

TOPS is also supporting the development of optimization algorithms for
the Toolkit for Advanced Optimization (TAO) and the linkage of these
tools to applications through a component software interface. The
TaoSolver component in Figure 2 has been developed in collaboration with
the Center for Component Technology for Terascale Simulation Software
(CCTTSS) and has enabled the high-performance computational chemistry
packages NWChem from Pacific Northwest National Laboratories and MPQC
from Sandia National Laboratories to interact with the TAO solvers. New
capabilities have been added to the TAO component interface so that
these and other problems can be solved on parallel machines.

![](media/image3.jpeg){width="3.1902777777777778in"
height="1.3284722222222223in"}

*Figure 2. The TaoSolver interface components*

The work in TAO was highlighted in a demonstration at SC2003 that
featured interactions between electronic structure components based on
NWChem and MPQC for energy, gradient, and Hessian computations;
optimization components based on TAO; and linear algebra components
based on Global Arrays (developed at PNNL) and PETSc. This work has
enabled applications to benefit from innovative algorithms in the field
of optimization. Initial benchmarking of the solvers has demonstrated
good performance on serial architectures and scalability on parallel
architectures. In particular, on a benchmark Lennard-Jones application
with 65,536 atoms, TAO achieved a speed-up factor of 156 on 170
processors.

Related algorithmic work includes the addition of a semi-smooth Newton
method for bound-constrained variational inequalities. We have also
shown that even first-order methods, such as limited-memory methods for
bound-constrained problems, can use mesh sequencing techniques to reduce
solution times by a full order of magnitude.

![](media/image4.png){width="2.7215277777777778in"
height="2.0479166666666666in"}

*Figure 3. Ground state of the Henon equation on the annulus computed by
the elastic string algorithm.*

TOPS is also developing novel algorithms for computational chemistry, in
particular, the elastic string algorithm for computing mountain passes
and transition states. This algorithm can be used, for example, to
compute nontrivial solutions to an important class of semilinear partial
differential equations and to determine the transition state for
chemical reactions. Figure 3 displays the ground state for the Henon
problem calculated with the elastic string algorithm.

The TOPS project webpage may be found at
[http://www.tops-scidac.org](http://www.tops-scidac.org/).

**For further information on this subject contact:**

Professor David E. Keyes, Project Lead

Columbia University

Phone: 212-854-1120

david.keyes@columbia.edu