Notes and observations on software for (mostly) scientific applications.
Thursday, June 10, 2004
G. W. Stewart has created Matran, a matrix wrapper for Fortran 95, to make it easier to do matrix computations within Fortran 95.
I would like to announce the availability of Matran (pronounced
MAY-tran), a Fortran 95 wrapper that implements matrix operations and
computes matrix decompositions using Lapack and the Blas. Although
Matran is not based on a formally defined matrix language, it provides
the flavor and convenience of coding in matrix oriented systems like
Matlab, Octave, etc. By using routines from Lapack and the Blas,
Matran allows the user to obtain the computational benefits of these
packages with minimal fuss and bother.
Matran has the following features.
- Matran supports computation with general, diagonal, triangular,
Hermitian, and positive definite matrices. Empty matrices are
- Matran uses overloaded and defined operators to implement
the common matrix operations, including manipulations with
partitioned matrices. In addition, Matran provides functions
and constructors for norms, random matrices, etc.
- Matran supports the following matrix decompositions: Pivoted
LU, Cholesky, QR, pivoted QR, spectral, SVD, real Schur,
- Matran allocates memory automatically, attempting to reuse
memory whenever possible. It provides a systematic way for
deallocating memory when it must be done by the programmer.
- Matran is an open package. It is easy to add new capabilities.
A big problem with current MPI implementations is their lack of fault tolerance. If one of the computing nodes goes down, any parallel MPI jobs using that node will also crash.
The FT-MPI project aims to remedy that situation.
Fault Tolerant MPI (FT-MPI) is an independent implementation of the MPI 1.2
message passing standard that has been built from the ground up offering
both user and system level fault tolerance. The FT-MPI library gives
application developers the ability to build fault tolerant or survivable
applications that do not immediately exit due to the failure of a processor,
node, or MPI task. To reach this goal, FT-MPI extends the current MPI
specification, playing a leading role in current world-wide efforts to
improve the error-handling of MPI applications.
FT-MPI is an efficient MPI implementation of the MPI standard and its
performance is comparable to other public MPI implementations. This has been
achieved though the use of optimized data type handling, an efficient point
to point communications progress engine and highly tuned and configurable
The first full FT-MPI release was announced at the SC2003 Conference in
Phoenix November 2003. This release included all the functions defined in
the MPI 1.2 document as well as several sections of the MPI 2
specifications. The release was validated by the IBM, Intel, PACX, MPICH,
BLACS and ScaLAPACK test suites. Performance comparisons have been made
using the HPC Challenge Benchmarks (http://icl.cs.utk.edu/hpcc/) . A number
of fault survivable numeric applications have also been developed and are
distributed as user modifiable examples.
I've found another freely available MATLAB-esque package. This one's from the functional language community. It's called PsiLAB and is based on the
PsiLAB is written mainly in the functional language O'CaML developed at INRIA research laboratories. It's mainly made of three parts:
- An interpreter, of course O'CaML itself
- libraries written in O'CaML,
- external libraries written in Fortran and C.
Main features of PsiLAB are:
- All O'CaML functions and data types are supported,
- support for different data types: float, int, complex
- extensive matrix package
- 2D and 3D plot package with graphical or postscript output
- various generic and special mathematical functions
- linear algebra package (solving of linear equation systems and linear least square problems)
- Linear Regression
- non linear least square fit routines
- Fast Fourier Transformations
- some image processing functions
- online help system, easily extensible by user functions
- easy to extend for people knowing basics about the O'CaML C extension facilities
PsiLAB uses the following external libraries, mainly written in Fortran:
- LAPACK: Linear algebra and linear least square problems
- MINPACK: Non linear least square fits
- PLPLOT: 2D and 3D plot library with several output drivers (X11, PS, Xfig,...)
- FFTW: Fastest Fourier Transform in the West (and the East ?)
- AMOS: Several special functions: Bessel Polynomials and more ...
- SLATEC (partially implemented): More special functions (Gamma function,...)
- CamlImages (partially implemented): Support for various image formats
PsiLAB is not only written in O'CaML, it is CaML. That means: if you are familar with this programming language, you can write PsiLAB programs. And you can do all things with PsiLAB you can do with the generic O'CaML development system:
- using modules for access to data base servers
- creating new develop environments
- writing lexers and parsers (perhaps with mathematical background)
- more sophisticated image processing
- http servers (with direct access to your computation results ?)
- and many more ...
The CaML interpreter system, which is in reality a pure compiler concept, was chosen because of the high computation speed of this system and the high portability. You have the advantages of an interpreter like language (from the user point of view), but with performance comparable with C/C++ programs. All functions will be translated by the CaML compiler into a system and machine independent Byte Code. This Byte Code will be then executed on a virtual machine. Currently, you have a terminal driven environement with online help. Plots are printed to an additional X11 window or to a postscript file.
A new version of PLTMG is available.
PLTMG 9.0 is a package for solving elliptic partial differential
equations in general regions of the plane. It is based on continuous
piecewise linear triangular finite elements. PLTMG features several
adaptive meshing options and an algebraic multilevel solver for the
resulting systems of linear equations. PLTMG provides a suite of
continuation options to handle PDEs with parameter dependencies.
It also provides options for solving several classes of optimal
control and obstacle problems. The package includes an initial
mesh generator and several graphics packages. Support for the
Bank-Holst parallel adaptive meshing paradigm is also provided.
PLTMG is provided as Fortran (and a little C) source code, in both
single and double precision versions. The code has interfaces to
X-Windows, MPI, and Michael Holst's OpenGL display tool SG. The
X-Windows, MPI, and SG interfaces require libraries that are NOT
provided as part of the PLTMG package.
The Harminv library for harmonic inversion has been released.
Harminv is a free program (and accompanying library) to solve the problem of harmonic inversion — given a discrete-time, finite-length signal that consists of a sum of finitely-many sinusoids (possibly exponentially decaying) in a given bandwidth, it determines the frequencies, decay constants, amplitudes, and phases of those sinusoids.
It can, in principle, provide much better accuracy than straightforwardly extracting FFT peaks, essentially because it assumes a specific form for the signal. (Fourier transforms, in contrast, attempt to represent any data as a sum of sinusoidal components, and are thus limited by the uncertainty principle.) It is also often more robust than directly least-squares fitting the data (which can have problematic convergence), since it re-expresses the problem in terms of simply finding the eigenvalues of a small matrix.
Harminv uses a low-storage "filter diagonalization method" (FDM) for finding the sinusoids near a given frequency interval.
This kind of spectral analysis has wide applications in many areas of physics and engineering, as well as other fields. For example, it could be used to extract the vibrational or "eigen" modes of a system from its response to some stimulus, and also their rates of decay in dissipative systems. FDM has been applied to analyze, e.g., NMR experimental data. It is especially appropriate for analyzing numerical simulations, e.g. of quantum mechanics or classical electromagnetism. In general, it is useful when you know on physical grounds that your system consists of a small number of decaying & oscillating modes in the bandwidth of interest, and is not appropriate to analyze more arbitrary waveforms.
Version 5.0 of deal.II,
a finite element Differential Equations Analysis Library, has been released.
deal.II is a C++ program library targeted at adaptive finite elements and error estimation. It uses state-of-the-art programming techniques of the C++ programming language to offer you a modern interface to the complex data structures and algorithms required for adaptivity and enables you to use a variety of finite elements in one, two, and three space dimensions, as well as time-dependent problems.
The main aim of deal.II is to enable development of modern finite element algorithms, using among other aspects sophisticated error estimators and adaptive meshes. Writing such programs is a non-trivial task, and successful programs tend to become very large and complex. We therefore believe that this is best done using a program library that frees the application programmer from aspects like grid handling and refinement, handling of degrees of freedom, input of meshes and output of results in graphics formats, and the like. Also, support for several space dimensions at once is included in a way such that programs can be written independent of the space dimension without unreasonable penalties on run-time and memory consumption.
Among other things, it offers:
- Support for one, two, and three space dimensions, using a unified interface that allows to write programs almost dimension independent.
- Handling of locally refined grids, including different adaptive refinement strategies based on local error indicators and error estimators.
- Support for a variety of finite elements, including Lagrange elements of order one through four, discontinuous elements, Nedelec elements, and elements composed of other elements.
- Extensive documentation: all documentation is available online in a logical tree structure to allow fast access to the information you need. If printed it comprises more than 400 pages of tutorials, several reports, and presently some 3,800 pages of programming interface documentation with explanations of all classes, functions, and variables. All documentation comes with the library and is available online locally on your computer after installation.
- Modern software techniques that make access to the complex data structures and algorithms as transparent as possible. The use of object oriented programming allows for program structures similar to the structures in mathematical analysis.
- Fast algorithms that enable you to solve problems with up to several millions of degrees of freedom quickly. As opposed to programming symbolic algebra packages the penalty for readability is low.
- A complete stand-alone linear algebra library including sparse matrices, vectors, Krylov subspace solvers, support for blocked systems, and interface to other packages such as PETSc and METIS.
- Support for several output formats, including many common formats for visualization of scientific data.
LAPACK AND SCALAPACK TO BE UPDATED
Jack Dongarra et al. are in the process of updating the venerable LAPACK and
ScaLAPACK packages and want feedback from the user community.
We plan to update the LAPACK and ScaLAPACK libraries and would like to have
feedback from users on what functionalities they think are missing and would
be needed in order to make these libraries more useful for the community. We
invite you to enter your suggestions in the form below. It would be most useful
to have input by June 16th, although we would welcome your input at any time.
Both LAPACK and ScaLAPACK provide well-tested, open source, reviewed code
implementing trusted algorithms that guarantee reliability, efficiency and
accuracy. Any new functionality must adhere to these standards and should
have a significant impact in order to justify the development costs. We are
also interested in suggestions regarding user interfaces, documentation,
language interfaces, target (parallel) architectures and other issues, again
provided the impact is large enough.
We already plan to include a variety of improved algorithms discovered over
the years by a number of researchers (e.g. faster or more accurate
eigenvalue and SVD algorithms, extra precise iterative refinement, recursive
blocking for some linear solvers, etc.). We also know of a variety of other
possible functions we could add (e.g. updating and downdating
factorizations), but are uncertain of their impact.
Please see http://icl.cs.utk.edu/lapack-survey.html for the survey.
We would like to have your input by June 16th, 2004.
AXIOM NOW AVAILABLE
A while back I mentioned that the source code for the former commercial symbolic math package Axiom was going to be made available in the near future. Well, we're there, and
here it is. Additional documentation can be found
Axiom is a general purpose Computer Algebra system. It is useful for research and development of mathematical algorithms. It defines a strongly typed, mathematically correct type hierarchy. It has a programming language and a built-in compiler.
Axiom has been in development since 1971. At that time, it was called Scratchpad. Scratchpad was a large, general purpose computer algebra system that was originally developed by IBM under the direction of Richard Jenks. The project started in 1971 and evolved slowly. Barry Trager was key to the technical direction of the project. Scratchpad developed over a 20 year stretch and was basically considered as a research platform for developing new ideas in computational mathematics. In the 1990s, as IBM's fortunes slid, the Scratchpad project was renamed to Axiom, sold to the Numerical Algorithms Group (NAG) in England and became a commercial system. As part of the Scratchpad project at IBM in Yorktown Tim Daly worked on all aspects of the system and eventually helped transfer the product to NAG. For a variety of reasons it never became a financial success and NAG withdrew it from the market in October, 2001.
NAG agreed to release Axiom as free software. The basic motivation was that Axiom represents something different from other programs in a lot of ways. Primarily because of its foundation in mathematics the Axiom system will potentially be useful 30 years from now. In its current state it represents about 30 years and 300 man-years of research work. To strive to keep such a large collection of knowledge alive seems a worthwhile goal.
Efforts are underway to extend this software to (a) develop a better user interface (b) make it useful as a teaching tool (c) develop an algebra server protocol (d) integrate additional mathematics (e) rebuild the algebra in a literate programming style (f) integrate logic programming (g) develop an Axiom Journal with refereed submissions.
The Axiom sources are now available for anonymous download. The system builds correctly on Redhat Linux 9.
For those who want to jump on the XML bandwagon but aren't willing to give up all their neat
TeX stuff, there's TeXML, an XML vocabulary for TeX. There's also a Python processor that translates TeXML source into TeX.