Victor Eijkhout and Jack Dongarra
In this chapter we discuss numerical software for clusters. We focus on some of the most common numerical operations: linear system solving, eigenvalue computations, and fast Fourier transform.
Numerical operations such as linear system solving and eigenvalue calculations can be applied to two different kinds of matrix: dense and sparse. In dense systems, essentially every matrix element is nonzero; in sparse systems, a sufficiently large number of matrix elements is zero that a specialized storage scheme is warranted; for an introduction to sparse storage, see . Because the two classes are so different, usually different numerical libraries apply to them. For dense systems, we discuss ScaLAPACK and PLAPACK as the choices for both system solving and eigenvalue computations. For sparse systems, we discuss Arpack for eigenvalue problems. There exist two classes of algorithms for solving sparse linear systems: direct methods and iterative methods. We will discuss SuperLU as an example of a direct solver and PETSc and Aztec as examples of iterative solvers.
Fast Fourier transforms (FFTs) typically are applied many times to different data. For FFTs we discuss the FFTW package (Section 12.4), which is probably better optimized than any other free FFT package.
In addition to numerical software operations, we discuss the issue of load balancing. We focus on two software packages, ParMetis and Chaco, which can be used in the above-mentioned sparse packages.
We conclude this chapter with a brief list of some popular science applications that run on Linux clusters, as well as a list of software for linear algebra that is freely available on the Web.
A practical point. Some of these packages are written in Fortran, some in C. While calling a Fortran package from C is relatively easy by observing linker naming conventions, the reverse direction can be difficult unless the package was designed to be called from Fortran. We will remark on the implementation language of each package, and the ease with which it can be interfaced to other languages.