Next: Approximating the Permanent
Up: Mathematical Algorithms and
Previous: Parallel Helmholtz Solvers
Roldan Pozo, ACMD
Jack Dongarra, Oak Ridge National Laboratory
Karin A. Remington, Scientific Computing Environments Division
Andrew Lumsdaine, University of Notre Dame
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
efficiency, so as to not waste a valuable resource. As a result,
much research has focused on issues of portability, flexibility,
performance, and software reuse for mathematical software development.
At NIST researchers have been working in object-oriented numerical computing to
design and develop reusable software components for solving a problem which is
at the core of much 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-Seidel, 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.
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 one thousand copies of LAPACK++, for
example, have been requested over the Internet by 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.
Next: Approximating the Permanent
Up: Mathematical Algorithms and
Previous: Parallel Helmholtz Solvers