PARA'04 State-of-the-Art
in Scientific Computing
June 20-23, 2004 (Home page)
Updated: 20 February 2004

"Oblio: Design and Performance"

Florin Dobrian and Alex Pothen

We describe Oblio, a library for solving sparse symmetric linear systems of equations by direct methods.

The code was motivated by our need to build a framework for the quick prototyping and testing of algorithmic ideas. As a consequence, flexibility was a major goal. We needed a code that is easy to understand, maintain and modify, features that that are not usually characteristic of scientific computing software.

Traditionally, solvers are designed to be efficient, and most of the time the design is not flexible enough to allow changes and additions. We decided to design Oblio to be both efficient and flexible. Obviously, we had to make trade-offs along the way.

While efficiency is generally guaranteed by the use of good algorithmic techniques, flexibility requires modern software engineering. Dynamic memory allocation, encapsulation, polymorphism, and templates are some of the techniques we use.

For efficiency, Oblio calls fast dense linear algebra kernels from BLAS and LAPACK. Except for that, the code is written entirely in C++. Templates are used in order to solve both real and complex valued problems.

Oblio is a supernodal solver that implements three major column-oriented algorithms for symmetric problems: left-looking, right-looking and multifrontal. Implementing several algorithms is not difficult due to the flexibility of the design; code for the common subproblems can be combined in different ways to obtain code for the three algorithms.

The flexibility of Oblio can be further illustrated by the choices it offers. We provide three types of factorizations: two static ones for positive definite and indefinite matrices, respectively, and a dynamic one for indefinite matrices. In addition, three factor data structures are available: in-core static, in-core dynamic, and out-of-core. The implementation effort required by all the combinations between algorithms and data structures is significantly reduced through polymorphism.

It is important to understand that, by providing all these options, we are able to choose the algorithm, data structure, and memory management policy that yield the best performance for a given problem, on a given computational platform.

Several other features are of interest in Oblio. By using a dynamic data structure for the elimination forest it is very easy to reorder for storage optimization and to amalgamate supernodes for faster computations. The dynamic factorization of indefinite matrices uses both 1-by-1 and 2-by-2 pivots. We can also perform iterative refinement and we can solve systems with multiple right-hand-sides.

Oblio continues to be actively developed. Future extensions include dynamic factorization with larger pivots as well as some static pivoting techniques.

In this talk we discuss the major design issues that support flexibility in Oblio and we use a set of test problems to illustrate the performance as well as the numerical properties of the solver.

Home page