Algebraic Java classes for optimization

Matthias Schwab and Joel Schroeder

matt@sep.stanford.edu, schroeder@alumni.stanford.org

ABSTRACT

Our software, Jest, comprises a general and extendible library for numerical optimization for science and engineering, Jam, and a particular extension of that framework for seismic image processing, Jag. Jest successfully separates optimization and application software without imposing limitations on an application's vector representation, on an application's operator implementation, or on a solver's ability to manipulate vectors and operators. To ensure the compatibility of solver and application, Jest includes a set of simple interfaces that define method invocations for the fundamental mathematical objects of numerical optimization, such as vectors, vector spaces, operators, and solvers. Jest's solvers are implemented in terms of these mathematical objects and consequently possess the generality of the original abstract mathematical algorithm. Jest's seismic imaging library, Jag, demonstrates that Jest incurs no restrictions and little or no programming overhead for scientific or engineering software packages. While generally implemented in Java, Jest links some computationally intensive applications to C-routines to improve performance. Once Jest is integrated in our laboratory's electronic book, our research becomes reproducible by the push of a button in any world-wide-web browser.

Jest (Java for estimations) separates optimization and application software without imposing limitations on either. Consequently, experts independently implement complementary and reusable optimization and application software, irregardless of the algorithms' internal complexity. The Jest library is accompanied by a growing number of examples and solvers. This chapter is an advertisement for the Jest software: my current version of Jest is available at my website.

Off-the-shelf optimization packages are usually limited to particular implementations and to somewhat arbitrary calling sequences. Off-the-shelf optimization packages usually implement their vectors in simple generic data structures, such as one-dimensional Fortran arrays. Unfortunately, generic data structures are often inconvenient or unacceptable in the case of complicated vectors or vectors too large to hold in-core. Alternatively, laboratories develop their own in-house optimization software that they adapt to their local data structure and application type. This approach, however, locks a laboratory into a fixed data structure and application style while simultaneously preventing any collaboration with laboratories of a different standard. Additionally, any new routine has to comply with the calling sequences of existing routines. A new routine can easily take advantage of old programs by invoking their known calling sequence. However, a new routine is not easily substituted for an existing alternative unless the two programs share identical calling sequences: a coincidence that is not easily maintained among a diverse group of contributing programmers.

Jest is centered around a set of abstract mathematical interface classes - Jam (Java for mathematics) - that resolve the implementation- and invocation-compatibility problem of traditional optimization libraries. Rather than defining a specific data representation, Jam defines the functionality of basic numerical analysis objects, such as vectors, vector spaces, operators, and solvers. Jam does not contain any implementations but consists of a collection of Java interfaces that assign names and methods to each of Jest's mathematical objects. The central Jam package is the only part of Jest that is shared by all users (see Table 1). All other Jest packages implement Jam interfaces. The individual The Javadoc pages available at our web page are

Jam interfaces do not prescribe any particular implementation, such as a vector representation. Collaboration among classes relies on the method invocations defined by the Jam interface. For example, Jam's vector interface requires all vectors to implement the simple Hilbert vector operations such as addition of two vectors, scaling of a vector, or the computation of the norm of a vector. A Jam-compatible class implements a Jam interface and limits itself to use only Jam-defined interface methods. a programmer of a Jest class is not concerned with the implementation or invocation of other Jest classes, but only with the invocation of the relevant Jam interfaces. Furthermore, the Java compiler ensures that any class that implements a Jam interface does indeed supply all necessary methods. Consequently, a programmer can, in principle, interchange all classes that implement the same Jam interface.

But how can one define a complete and general set of Jam interfaces? Mathematics! Jam defines names and method invocations for basic mathematical entities (vectors, operators, and solvers) and their standard operations. Ultimately, the Jam interface is as complete and general as the original mathematical definition. Furthermore, the mathematical framework of Jest is shared by researchers in numerical analysis, engineering, and natural sciences. A perfect interface design! However, only a full-blooded object-oriented language allows the necessary abstract formulation.

Overall, Jam offers a plug-and-play quality: a programmer can accept or replace any part of Jest and preserve compatibility by implementing the corresponding Jam interfaces. Finally, Jam is not only general by not imposing a specific implementation, it is also extendible by allowing new mathematical object interfaces to be added.

Jest packages (class libraries) are separated by user community. The top package, Jam, is shared by all users and only includes interfaces for the abstract mathematical entities, such as a vector and its operations (add, scale, etc.). User groups (e.g., my laboratory's geophysicists) author packages the classes of which implement Jam interfaces. For example, Jag's Rsf class is my laboratories data structure and implements the Jam vector interface. The Juice package contains my elementary numerical analysis classes (e.g., my conjugate gradient solver). The bottom two packages do not exist but represent potential extensions by other user groups. Packages are bound to be compatible since they implement Jam interfaces. Consequently, any given user package only implements the classes that are unique to its user community. Jest's extendible structure and mathematical objects aims to garner collaboration across disciplines.

 

Package User Group Class type Vectors Operators Solvers name

Anyone Interfaces Vector Operator Solver

of abstract math objs CompoundOperator IterativeSolver

Mathematicians Classes of Rn MatrixMultiplication CG solver,

numerical analysis Newton-Raphson ..

SEP Classes of seismic Rsf, Isf Nmo, convolution ...

geophysicists processing

2nd research Classes of seismic Kirchhoff migration ... Arnoldi solver ...

geophysicists processing

Chemists ... ... ... ...

 

Jest's Juice package contains implementations of Jam interfaces: general solver classes (e.g., a conjugate-gradient solver), simple vector and space classes (e.g., a space of real numbers), simple operator classes (e.g., a zero and an identity operator), and classes of compound vectors and operators that wrap their components into a single vector respectively operator (e.g., product vector or block operator). Since Juice classes are mostly trivial, light-weight implementations, we expect most Jest programmers to use them independent of their particular application.

Finally, the Jag (Java for geophysics) group of packages contains vectors and operators for seismic image processing. Jag is centered around the Rsf (Regularly Sampled Function) vector class. An Rsf vector represents a multi-dimensional regularly sampled, physical functions and is similar to a traditional float array type. An array of axis objects describes the Rsf vector space. Additionally, Jag comprises several seismic image processing packages based on Rsf vectors, e.g., convolution, edge detection, nonstationary patching, and missing data estimation. Within the Jest optimization framework, Jag's vector and operator implementations constitute a budding seismic processing library.

Java is a fun programming language. We struggled for years to develop an objected-oriented optimization and imaging package in C++, but our Fortran-programming colleagues found C++ too complex and difficult to master. We consider Java easy to program and hope, as Jest grows and prospers, some of our colleagues will join our effort.

We have little experience with off-the-shelf optimization packages since our laboratory, the Stanford Exploration Project, maintains its own small collection of optimization routines. It is this isolation of researchers and laboratories that Jest sets out to overcome. However, I will first list some brief and brash historic and technical comments on a few alternative libraries for contrast and comparison.

Jest is not the first library that attempts to separate solver and application software. Examples of well-known high-quality optimization libraries are MINOS () and MINPACK (). However, these libraries are defined in procedural languages and impose severe restrictions on the application software. To the contrary, Jest does not require any particular implementation of any of its objects. It only requires that an object's mathematical operations are implemented somehow.

Historically, Jest is the latest in a series of optimization libraries. Our laboratory developed CLOP 1993, an experimental geophysical inversion library implemented in C++. CLOP enabled Lumley et al. Lumley et al. (1994) to prototype a new multiple suppression scheme that probably would not have been attempted in our laboratory's traditional Fortran environment. Nichols and Dye redesigned CLOP's class hierarchy to express abstract objects of vector algebra. Independently Gockenbach and Symes of the Rice Inversion Project developed a similar C++ library. In 1994, the efforts of the two laboratories merged into the Hilbert Class Library (HCL) Schwab (1994). Gockenbach published HCL Gockenbach and Symes (1996) and since maintains a detailed web-page Gockenbach (1996). Jest began as a Java implementation of HCL. We found Java much easier to use and learn than C++: an important fact for traditional Fortran or C programmers.

Lydia Deng et al.  (); Deng et al. (1996) developed a C++ optimization library for geophysical inversion that addresses similar problems as Jest. Fomel Fomel et al. (1996); Fomel and Claerbout (1996) focused on performance and implemented a geophysical optimization library in Fortran90 using its modular features.

In the summer of 1996 (before the development of Jest), SEP held an informal conference on objected-oriented numerics Claerbout and Biondi (1996). Afterwards, several participants cooperated to develop a framework to combine HCL's C++ classes with high-performance Fortran90 routines. The required linking of Fortran90 and C++ proved difficult but doableSchroeder and Schwab (1996); Urdaneta and Karrenbach (1996).

Fall 1997, Jacob and Karrenbach 1997 implemented a multi-threaded velocity estimation based on Jest.