TOPS Software for Optimization of Simulated Systems

PIs: V. Akçelik², S. Benson¹, G. Biros³, X. Cai⁵, O. Ghattas², D. Keyes⁴, J. Moré¹, T. Munson¹, J. Sarich¹, B. Smith¹
Principal affiliates: L. C. McInnes (CCTTSS), P. Hovland (PERC) ¹ Argonne National Lab, ² Carnegie Mellon U., ³ Columbia U., ⁴ New York U., ⁵ 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.

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 left image shows an isosurface from the target basin used to generate synthetic surface seismograms. The right 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.

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.

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 .

For further information on this subject contact:
Professor David E. Keyes, Project Lead
Columbia University
Phone: 212-854-1120
david.keyes@columbia.edu

back to project page