Collaborative Research: Large-scale Optimization: Matrix-free Algorithms, Data Parallelism, and Applications in Seismic Inversion

点击翻译按钮获取中文摘要

In this collaborative interdisciplinary project, theinvestigators Mark Gockenbach, Anthony Kearsley, and WilliamSymes develop and implement algorithms for large-scaleoptimization problems that arise in a variety of applications,focusing on techniques particularly suited to parallelarchitectures, and apply the methods to the seismic velocityestimation problem. Large-scale optimization problems oftenpresent difficulties to standard algorithms and software. Manyof these difficulties arise in the seismic velocity estimationproblem. First, the sheer data volume makes it impractical toexplicitly form and factor matrices, as required by many standardoptimization algorithms. To address this, a new matrix-freeSequential Quadratic Programming (SQP) algorithm is developed,based on recent advances in matrix-free algorithms for theso-called trust region subproblem. Second, the data structuresand interfaces required for seismic data processing are noteasily adapted to those required by "off-the-shelf" optimizationsoftware. The Hilbert Class Library (HCL), an object-orientedoptimization package, can solve optimization problems involvingdata structures and interfaces of arbitrary complexity. The SQPalgorithm, along with the necessary seismic data structures andsimulators, is implemented in HCL. Third, large-scalesimulations often require the use of parallel computation. Theuse of parallelism in simulation and optimization is addressedthrough the development of HCL classes that automaticallydistribute data over a network of distributed workstations. Theabove innovations in optimization methods and software are usedto study in detail a new formulation of the seismic inverseproblem. The investigators have recently introduced thisformulation in order to overcome certain optimization-theoreticdifficulties inherent in standard formulations. Optimization problems arise in science and engineering,where one often wishes to find the best design, the bestmathematical model, the best strategy, and so forth. Large-scaleoptimization problems, which involve many variables, presentspecial challenges, including the choice of algorithm, therepresentation of data, and the interface between optimizationsoftware and programs written by the application scientist. Thisproject addresses these challenges in the context of an importantapplication, seismic exploration. The investigator and hiscolleagues develop new optimization algorithms to identifygeological features of the subsurface of the earth. Included isa general method for solving large-scale optimization problems;this algorithm is applicable to other science and engineeringproblems. Moreover, they also develop an innovative softwarepackage, called the Hilbert Class Library (HCL), that allowsoptimization algorithms to be used with problems of arbitrarycomplexity; the software adapts to different data structures andsoftware interfaces. Finally, they extend HCL to automaticallytake advantage of parallel computers, making it easier to takeadvantage of high performance hardware. The seismic explorationproblem is important to the petroleum industry; a preciseknowledge of geological structures is essential for efficientutilization of petroleum reserves. In addition, the HCL softwareaddresses the important issue of technology transfer as itpertains to numerical algorithms; too often algorithmic advancesare unavailable to application scientists because optimizationsoftware and application software have incompatible interfaces.