Object Oriented Numerical Software

The cost of large-scale software development and maintenance, particularly for scientific computing on high performance and parallel architectures, has been steadily increasing. Furthermore, performance tuning of numerical programs is becoming more complex, while application users are demanding broader portability across constantly-changing architectures. At the same time, large investments made in parallel and supercomputers put a strong emphasis on requiring applications to run efficiently, thus not wasting a valuable resource.

Much research activity has focused on issues of portability, flexibility, performance, and software reuse for mathematical software development. NIST researchers have been working in object oriented numerical computing to design and develop reusable software components for solving one major portion of scientific computing: systems of linear equations. The ongoing research is focusing on several areas:

• Iterative solution of large linear systems. The Iterative Methods Library, IML++, is a collection of algorithms implemented in C++ for solving both symmetric and nonsymmetric linear systems and linear least squares problems using iterative and semi-iterative techniques. Included are traditional algorithms, such as Jacobi and Gauss-Siedel, together with more powerful modern methods: Chebyshev iterations, conjugate gradient (CG), conjugate gradient squared (CGS), biconjugate gradient (BiCG), biconjugate gradient stabilized (BiCGSTAB), generalized minimum residual (GMRES), and Quasi-Minimal Residual (QMR). The advantages of a C++ design include having a single template algorithm provide support for arbitrary matrix classes (e.g. dense, sparse, banded, distributed). This provides for more natural ``mathematical'' interfaces, making the resulting codes more readable, and dramatically cutting software maintenance costs.

• Sparse Matrix Objects. SparseLib++ is a collection of C++ classes for unstructured sparse matrices and currently includes compressed row, compressed column, and coordinate storage formats. These sparse matrix objects become an ``extension" of the C++ language; that is, they can be assigned, operated on, and indexed as if they were a basic data type. The Sparse BLAS Toolkit is used to achieve efficient kernel mathematical operations (e.g. sparse matrix-vector multiply) and to enhance portability and performance across a wide range of computer architectures. Included in the package are various preconditioners used in iterative solvers for linear systems of equations.

• Direct Matrix Factorizations LAPACK++ is an object-oriented extension to the Fortran linear algebra package LAPACK for solving dense and banded linear systems of equations and linear least squares and eigenvalue problems. LAPACK++ provides a framework for describing general block matrix computations in C++ to take advantage of the Level 3 BLAS for optimal performance across a wide range of computational platforms. Without a proper design of fundamental matrix and factorization classes, the performance benefits of blocked codes can be easily lost due to unnecessary data copying, inefficient access of submatrices, and excessive run-time overhead in the dynamic-binding mechanisms of C++. LAPACK++ addresses these potential problems and provides performance comparable to optimized Fortran 77 on most platforms.

• Matrix and Vector Classes MV++ is a core library of fundamental numerical matrices and vectors which are used as building blocks for SparseLib++ and LAPACK++. They provide basic ``Fortran 90" array capabilities, including index triplet notation, matrix operations, and basic computational kernels. MV++ also provides aliasing and referencing mechanisms, as well as copy-by-value semantics.

• Integrated C++ Solutions for Linear Algebra Programming The Template Numerical Toolkit (TNT) for Linear Algebra utilizes the latest capabilities of C++ -- templated functions and classes, and basic data structures from the Standard Template Library (STL) -- to provide an integrated collection of generic matrix/vector classes based on components of STL, together with specialization of generic algorithms for maximal efficiency by incorporating the best aspects of the Lapack++, MV++, IML++, and SparseLib++ packages described above.

In industry and research, there has already been much interest in object oriented technology for reducing the high cost of numerical software development and maintenance. Over ten thousand Internet accesses to the LAPACK++ library, for example, have been logged from universities, academic research centers, and high technology companies. Concurrent Technologies Corporation is one such company which is testing an early version of the SparseLib++ and IML++ libraries to solve image processing problems arising in neurosurgery. Other developers are interested in distributed memory versions of SparseLib++ for solving large scale linear systems on parallel architectures such as the Cray T3D.