q10. S.C., Numerical Analysis, and Associated Fields Resource Guide
This is a summary of Internet-related resources for
a handful of fields related to Scientific Computing, primarily:
* scientific and engineering numerical computing
* numerical analysis
* symbolic algebra
* statistics
* operations research
This FAQ is available at:
http://www.mathcom.com/corpdir/techinfo.mdir/index.html www.mathcom.com
A text version of the entire FAQ in a single file is available at:
iii q999, "Entire FAQ".
Table of Contents:
* iii q20, "Introduction"
* iii q30, "Overview of Recent Additions"
* iii q50, "Acknowledgements"
* iii q105, "What is Numerical Analysis?"
* iii q110, "Indices of NA Software on the Net"
* iii q115, "NA Software Libraries on the Net"
* iii q120, "NA Software Packages on the Net"
* iii q125, "Commercial NA Libraries and Packages"
* iii q135, "Newsgroups for NA"
* iii q140, "Professional Societies for NA"
* iii q145, "Electronic Newsletters for NA"
* iii q150, "Electronic Journals for NA"
* iii q155, "Online Papers for NA"
* iii q160, "Miscellaneous Web Sites for NA"
* iii q165, "Books, With and Without Software, for NA"
Specialized Subfields Within Numerical Analysis
* iii q205, "Dense Linear Algebra Systems"
* iii q207, "Sparse Linear Algebra Systems"
* iii q210, "Random Number Generators (RNGs)"
* iii q215, "Function Evaluation"
* iii q220, "Finding Roots"
* iii q230, "Curve Fitting, Data Modelling, Interpolation, Extrapolation"
* iii q240, "Transforms (FFT, etc) and digital signal processing (DSP)"
* iii q245, "Wavelets"
* iii q250, "Integration and Ordinary Differential Equations (ODEs)"
* iii q253, "Stochastic Differential Equations"
* iii q255, "N-Body and Particle Simulation"
* iii q260, "Partial Differential Equations (PDEs) and Finite Element Modeling (FEM)"
* iii q265, "Operations Research: Minimization, Optimization"
* iii q267, "Queueing Theory and Performance Analysis"
* iii q270, "Computational Geometry"
* iii q275, "Interval Arithmetic"
* iii q285, "Plotting, Graphics and Scientific Visualization"
* iii q290, "Miscellaneous NA Software"
Associated Fields
* iii q505, "Probability and Statistics"
* iii q510, "Chaos Theory (Nonlinear Dynamics)"
* iii q520, "Symbolic Algebra"
* iii q530, "Cryptography (Cryptology)"
* iii q540, "Fractals"
* iii q550, "Neural Networks"
* iii q560, "Discrete algorithms"
* iii q570, "Constraints"
* iii q580, "Genetic Algorithms"
* iii q590, "Simulated Annealing"
Teaching and Academic Software
* iii q800, "Teaching and Academic Software"
Copyright 1995-2002 S. J. Sullivan.
This document(s) may be copied and/or reproduced providing that
the use is for non-commercial purposes only, and
all copies contain this paragraph and copyright notice.
The information contained in this document(s) is believed to be true
but no guarantees of accuracy are made, and there is no liability
of any sort for any consequences of its use.
Steve Sullivan
Mathcom, Inc.
info@mathcom.com
=========================================================================
q20. Introduction
Where to find this FAQ:
On the web:
http://www.mathcom.com Mathcom (under the "Tech Info" heading)
"[]" Reviews are associated with the name of the reviewer in brackets.
Those reviews marked [SJS] are by myself.
"[author]" indicates text taken from a package documentation.
Instead of the normal question/answer form, this FAQ is organized
as an outline ... hopefully, you'll find your questions answered here.
=========================================================================
q30. Overview of Recent Additions
There have been many updates since the last version; some are:
deal.II is a C++ class library targeted at adaptive finite elements.
See iii q260.5.20, "Deal.II"
Clemens Valens' wavelet tutorial and info.
See iii q245, "Wavelets"
SBmethod is a C++ code for large scale eigenvalue optimization.
See iii q265.1, "Optimization, Linear and Non-Linear Programming: General Resources"
The NEOS Optimization Server solvers offer online solution
of optimization problems.
Optimization problems are solved automatically with minimal
input from the user. Users only need a definition of the optimization
problem.
See iii q265.1, "Optimization, Linear and Non-Linear Programming: General Resources"
The ZunZun server offers online interactive fitting and
graphing for 2D and 3D data sets.
See iii q230.9, "ZunZun Interactive 2D and 3D Data Modeling"
GiNaC is an open framework for symbolic computation within the C++
programming language.
See iii q520.5.11, "Ginac"
Ch is an interpretor for C++ numerics.
See iii q125.17, "Ch Interpretor for C++ numerics"
UMFPACK is a package written in C for sparse LU factorization
See iii q207, "Sparse Linear Algebra Systems"
Mondriaan is a sparse matrix partitioning package.
See iii q207, "Sparse Linear Algebra Systems"
EigTool combines the Pseudospectra GUI with MATLAB's eigs command to
provide visualisation of the Arnoldi iteration during an eigs
computation.
See iii q207, "Sparse Linear Algebra Systems"
=========================================================================
q50. Acknowledgements
Many thanks to all those who've given their time and advice
in creating this FAQ. In order to save contributors from
unwanted spam, I do not include their email addresses.
Bob Berman
Ronald F Boisvert
Ted Brown
John Chandler
Luiz Henrique de Figueiredo
Bill Frensley
Pawel Gora
Amara Graps
Vijay Gupta
Doug Hart
Albert Hines
Charles Knechtel
Zdislav V. Kovarik
Dave Linder
George Marsaglia
Pierre Maxted
Allen Mcintosh
Sean O riordain
Daniel Pfenniger
Daniel Pick
Brian Ripley
Ramin Samadani
Robert Schneiders
Peter Somlo
Tim Strotman
N. Sukumar
Stephen Vavasis
Dave Watson
Many thanks also to the organizers of the many services
listed herein - Netlib, the NIST guide, NA-Net, CAIN, the NASA
Graphics site, and numerous other indices and informative web pages.
===========================================================================
q105. What is Numerical Analysis?
NA is the union of theoretical and computational investigation into
the computer solution of mathematical problems. NA generally includes
those problems involving continuous functions of real or complex
variables, as opposed to solely discrete variables and functions.
The mixing of theoretical and computational concerns leads to
a strong emphasis on algorithms: what are the time and memory
usage properties of a certain algorithm? What errors are introduced
by an algorithm?
The computational aspects of NA usually take place within
the scope of floating-point arithmetic, and are implemented on
machines ranging from super-computers through PCs to hand-calculators.
The theoretical aspects extend into fields such as Calculus,
Differential Equations, and Analysis. The field of Linear Algebra
is so often used to model physical systems that the theoretical
study of Linear Algebra is in itself often considered to be
NA at work.
Primary areas of theoretical concern in NA are:
* global/local error bounding
* stability of algorithms
* rates of convergence of algorithms
Primary areas of computational concern in NA are:
* roundoff error
* global/local error and its tolerance
* time and memory requirements of computation
* High Performance Computing (HPC)
* parallel computing
* architecture/platform specific details.
===========================================================================
q110. Indices of NA Software on the Net
For indices of packages oriented towards symbolic algebra,
see iii q520, "Symbolic Algebra".
ttt The NIST Guide to Available Mathematical Software (Formerly called GAMS)
http://gams.nist.gov/ NIST Guide to Mathematical Software
or telnet to: gams.nist.gov
[SJS]:
Maintained by National Institute of Standards and Technology (NIST)
An index and server for a wide variety of mathematical
software, including most of netlib (see iii q115.1, "Netlib").
Much of the software is in Fortran. If you prefer to speak C++ or C,
see iii q160.1, "C++ Resources",
and iii q115.2, "Fortran, C, and f2c".
[Ronald Boisvert]:
The main focus is on fine-grained software components, e.g.
subroutines, although information about some larger packages are
included. As of November 1995, nearly 10,000 components from more
than 90 packages have been cross-indexed using a detailed
tree-structured problem classification system. Both freely available
software (from netlib or developed at NIST) and commercial packages
(used by NIST) are indexed, although source code is available only for
non-commercial software.
http://www.mathtools.net/ Mathtools.net
Mathtools.net: Large tech computing portal.
http://SAL.KachinaTech.COM/ SAL
Scientific applications on Linux index.
http://www.netlib.org/utk/people/JackDongarra/la-sw.html Dongarra's Survey
Jack Dongarra's survey of freely available linear algebra software.
Compares many free linear algebra packages. Does not discuss
the many packages derived from these core solvers.
===========================================================================
q115. NA Software Libraries on the Net
Libraries are collections of source code, and source code packages.
Much of the code is in Fortran. If you prefer to speak C++ or C,
see iii q160.1, "C++ Resources",
and iii q115.2, "Fortran, C, and f2c".
The main library by far is iii q115.1, "Netlib".
For statistical software, the best resource is iii q115.3, "Statlib".
Other libraries are iii q115.4, "UCAR's Mathematical and Statistical Libraries"
and iii q115.5, "Hensa Unix Parallel Archive".
* iii q115.1, "Netlib, including LAPACK"
* iii q115.2, "Fortran, C, and the f2c Translator"
* iii q115.3, "Statlib"
* iii q115.4, "UCAR's Mathematical and Statistical Libraries"
* iii q115.5, "Hensa Unix Parallel Archive"
* iii q115.6, "Modula-3 NA Library"
* iii q115.7, "Forth Numerical/Scientific Library"
* iii q115.8, "Eiffel Numerical/Scientific Library"
* iii q115.9, "Lisp Numerical/Scientific Libraries"
* iii q115.10, "Java Numerical/Scientific Libraries"
* iii q115.11, "Bell Labs (Lucent) Libraries"
* iii q115.12, "PLAPACK: Parallel Linear Algebra"
* iii q115.13, "WGS: SLICOT Control Theory Libraries"
* iii q115.14, "GSL: GNU Scientific Library"
* iii q115.15, "ATLAS: Automatically Tuned Linear Algebra Software"
See also the sections on:
* iii q205, "Dense Linear Algebra Systems"
* iii q207, "Sparse Linear Algebra Systems"
===========================================================================
q115.1. Netlib, including LAPACK
NetLib is probably the world's largest repository of numerical
methods programs. It is located at Oak Ridge National Laboratory,
Knoxville, Tennessee, and at AT&T Bell Laboratories, Murray Hill, NJ.
email: send message "help" to either:
netlib@ornl.gov
netlib@research.att.com
http://www.netlib.org Netlib
Some gems of netlib:
LAPACK provides a wide variety of linear algebra functions:
http://www.netlib.org/lapack/ LAPACK home
http://www.netlib.org/lapack95/ LAPACK Fortran95 interface
http://www.netlib.org/clapack/ C version of LAPACK
http://www.netlib.org/java/f2j/ Java version of LAPACK, f2j at netlib
http://www.cs.utk.edu/f2j/ Java version of LAPACK, f2j at UTK
LAPACK++ is a C++ version of, sadly, only a subset of LAPACK.
LAPACK++ is work in progress, and hopefully the full
functionality of LAPACK will be supported soon.
ScaLAPACK is for distributed memory machines.
Machine/architecture dependent Basic Linear Algebra Subroutines
(BLAS) are the keystone of Netlib.
===================================
q115.2. Fortran, C, and the f2c Translator
For C++ and C resources, see iii q160.1, "C++ Resources".
Most of the programs in netlib are in Fortran. However, netlib
contains an excellent Fortran-to-C conversion utility, f2c.
While f2c produces working C code, it is visually complex
and ugly. Using f2c on a large package like LAPACK can require
a good deal of time to get all the options correct.
Fortunately, LAPACK has already be converted to C: see CLAPACK.
The utility f2c can also be invoked by email. Send email
to netlib@research.att.com, with the subject "execute f2c",
and body containing the non-confidential Fortran program to be converted.
But the email option is of use only for very small, simple programs,
since a resulting C program of any size must be linked with the
f2c libraries. Usually one will have to download the f2c package
anyway to generate the libraries. Generally it's easier
to download the f2c package, build the libraries and the
f2c conversion program, and do the conversion locally.
CAUTION: Programs created by f2c conversion use parameter passing
conventions different from most C or C++ programs. Their
callers must create the appropriate parameters before using them.
See the file f2c.ps in the f2c distribution.
A good description of this issue may also be found in
the "readme" file for clapack in netlib.
===================================
q115.3. Statlib
Statlib is a huge repository of statistics related software and info.
Probability, statistics, random variables, distribution functions.
http://lib.stat.cmu.edu/ Statlib at CMU
ftp://lib.stat.cmu.edu Statlib via ftp
email: send message "send index" to statlib@lib.stat.cmu.edu
===================================
q115.4. UCAR's Mathematical and Statistical Libraries
UCAR's libraries contain some overlap with netlib.
http://www.scd.ucar.edu/dig/software.html UCAR
===================================
q115.5. Hensa Unix Parallel Archive
General info, software, articles, etc., on parallel computing.
http://wotug.ukc.ac.uk/parallel/environments/pcn/ Hensa
===================================
q115.6. Modula-3 NA Library
http://m3.polymtl.ca/m3/pkg/contrib/m3na/ Modula-3 NA
This is a libraried collection of numerical analysis routines written
in Modula-3. Includes linear algebra, roots, ffts, and a bit
of statistics.
===================================
q115.7. Forth Numerical/Scientific Library
http://www.taygeta.com/fsl/sciforth.html Skip Carter's Forth Library at Taygeta
===================================
q115.8. Eiffel Numerical/Scientific Library
http://www.eiffel.com/products/math.html Commercial Eiffel library at I.S.E.
===================================
q115.9. Lisp Numerical/Scientific Libraries
http://stat.umn.edu/~luke/xls/xlsinfo/xlsinfo.html Lisp-Stat
http://setosa.uwaterloo.ca/~ftp/Quail/features.html U. Waterloo
http://eksl-www.cs.umass.edu/research/clip-clasp-overview.html instrumentation and statistical analysis packages
ftp://ftp.cs.cmu.edu/user/ai/lang/lisp/code/math/0.html CMU's library
===================================
q115.10. Java Numerical/Scientific Libraries
http://www.vni.com/products/wpd/jnl/jnl_1_0.html Visual Numerics' Java package
[author]:
JNL, a Numerical Library for Java, is a set of classes for the most
important numerical functions missing in Java. The library is
comprised of one numerical type class, Complex, and three categories
of numerical functions classes: the special functions class, the
linear algebra classes, and the statistics class. All classes use
double precision floating point as the underlying float type.
http://www.cs.utk.edu/f2j/ JLAPACK
[author]:
The JLAPACK project provides the LAPACK and BLAS numerical subroutines
translated from their Fortran 77 source into class files, executable by
the Java Virtual Machine (JVM) and suitable for use by Java programmers.
This makes it possible for a Java application or applet distributed on
the web to use established legacy numerical code that was originally written
in Fortran. The translation was accomplished using a special purpose
Fortran-to-Java (source-to-source) compiler.
http://www1.fpl.fs.fed.us/linear_algebra.html Linear Algebra for Statistics Java Package
http://math.nist.gov/javanumerics/jama/ JAMA
[author]:
JAMA is a basic linear algebra package for Java. It provides user-level classes for constructing and manipulating real, dense
matrices.
Five fundamental matrix decompositions are provided:
Cholesky Decomposition of symmetric, positive definite matrices
LU Decomposition (Gaussian elimination) of rectangular matrices
QR Decomposition of rectangular matrices
Eigenvalue Decomposition of both symmetric and nonsymmetric square matrices
Singular Value Decomposition of rectangular matrices
Not Covered. JAMA is by no means a complete linear algebra environment. For example, there are no provisions for matrices with
particular structure (e.g., banded, sparse) or for more specialized decompositions (e.g. Shur, generalized eigenvalue). Complex
matrices are not included. It is not our intention to ignore these important problems. We expect that some of these (e.g. complex) will
be addressed in future versions. It is our intent that the design of JAMA not preclude extension to some of these additional areas.
http://www.math.nist.gov/scimark SciMark Java numerical benchmark
[author]:
The SciMark benchmark consists of various kernels (FFT, Monte Carlo, sparse
matrix computation, finite-difference stencils, and LU factorization)
and is meant to provide an indication of how well Java environments
perform on numeric and scientific applications.
SciMark can be run interactively within your browser, or downloaded
to run in other Java environments. The web site includes bar-graph
comparisons between various computer/Java platforms, as well
as an archive of previous results.
===================================
q115.11. Bell Labs (Lucent) Libraries
http://www.bell-labs.com/topic/swdist/ Lucent's Software Libraries
Includes the following items:
- BL-QMR A Block-QMR Algorithm for Non-Hermitian Linear Systems With Multiple Right-Hand Sides
- fptest A Test of a Computer's Floating-Point Arithmetic Unit
- imd Multilayer optical properties: modeling and curve-fitting
- IQP Quadratic Programming
- PORT
The PORT Mathematical Subroutine Library is a
collection of Fortran 77 routines that address many
traditional areas of mathematical software, including approximation,
ordinary and partial differential equations, linear algebra and
eigensystems, optimization, quadrature, root finding, special
functions, and Fourier transforms, but excluding statistical
calculations. PORT stands for Portable, Outstanding, Reliable,
and Tested. See:
http://www.bell-labs.com/project/PORT/ PORT
- topo Surface topography analysis
===================================
q115.12. PLAPACK: Parallel Linear Algebra
http://www.cs.utexas.edu/users/plapack/ PLAPACK
[author]:
PLAPACK is an MPI based Parallel Linear Algebra Package (PLAPACK)
designed to provide a user friendly infrastructure for building
parallel dense linear algebra libraries.
The Users' Guide, "Using PLAPACK: Parallel Linear Algebra Package"
is available from The MIT Press.
WHAT IS DIFFERENT: PLAPACK provides three features not currently found
in other publically available parallel dense linear algebra libraries:
1) A matrix distribution that is a step towards one that is driven
by the natural distribution of an application,
2) An application interface for filling and querying matrices and
vectors,
3) A programming interface that allows the code to be written in
a way that closely resembles the way algorithms are naturally
explained, using object based (MPI-like) programming.
===================================
q115.13. WGS: SLICOT Control Theory Libraries
http://www.win.tue.nl/niconet/NIC2/slicot.html SLICOT
[author]:
The objectives of WGS are first to bring together the existing numerical
software for control and systems theory in a widely available library,
called SLICOT, and to extend this library to cover as far as possible the
area of industrial applications.
===================================
q115.14. GSL: GNU Scientific Library
http://www.gnu.org/software/gsl/gsl.html GSL
[author]:
The GNU Scientific Library (GSL) is a collection of routines for numerical computing in C.
The routines have been written from scratch over a five year period by the GSL team using modern coding conventions. The subject areas covered by the library include,
Complex Numbers Roots of Polynomials Special Functions
Vectors and Matrices Permutations Sorting
BLAS Support Linear Algebra Eigensystems
Fast Fourier Transforms Quadrature Random Numbers
Quasi-Random Sequences Random Distributions Statistics
Histograms N-Tuples Monte Carlo Integration
Simulated Annealing Differential Equations Interpolation
Numerical Differentiation Chebyshev Approximation Series Acceleration
Discrete Hankel Transforms Root-Finding Minimization
Least-Squares Fitting Physical Constants IEEE Floating-Point
===================================
q115.15. ATLAS: Automatically Tuned Linear Algebra Software
http://www.netlib.org/atlas/ ATLAS
The ATLAS (Automatically Tuned Linear Algebra Software) group is
pleased to announce ATLAS 3.2. ATLAS provides a complete, high performance
implementation of the BLAS library, and a small subsection of the LAPACK
library. Highlights of what's new in this release include:
SMP support via posix threads for Level 3 BLAS
Addition of infrastructure for user contribution of kernels, thus allowing for:
- SSE support
- 3DNow! support
- Speedups on ev6x, ev5x, UltraSparcs, IA64, and PowerPC architectures
In addition, the associated developer release (ATLAS 3.3) possesses
support for Intel's SSE2, allowing for maximal DGEMM performance of around
2 Gflop/s on a 1.5Ghz Pentium 4 (SSE1 provides a roughly 4 Gflop/s peak
SGEMM on the same machine). Prebuilt archives are available for many architectures,
including well-tested version of the developer release. In particular,
SSE2-enabled Pentium 4 libraries are available for both Linux and Windows.
ATLAS is a software package that will automatically generate highly
optimized numerical kernels for our commodity processors. As the underlying
computing hardware doubles its speed every eighteen months, it often takes
more than a year for software to be optimized or "tuned" for performance
on a newly released CPU. Users tend to see only a fraction of the power
available from any new processor until it is well on the way to obsolescence.
===========================================================================
q120. NA Software Packages on the Net
Packages generally include an NA library and an interpretive
language for a front end.
Also see iii q520, "Symbolic Algebra", for free symbolic algebra packages.
* iii q120.1, "Octave"
* iii q120.2, "RLaB"
* iii q120.3, "Scilab"
* iii q120.4, "Tela"
* iii q120.6, "Medal"
* iii q120.7, "Euler"
* iii q120.8, "Prophet"
* iii q120.9, "Yorick"
* iii q120.10, "SpYorick"
* iii q120.11, "PETSc"
* iii q120.12, "The Blitz++ Numerical Library Project"
* iii q120.13, "Ascend"
* iii q120.14, "Algae, formerly called Alki"
===================================
q120.1. Octave
http://www.octave.org Octave
[Dave Lindner]: Octave is considered the closest-to-Matlab
of the Matlab clones.
[author]:
Octave is a high-level language, primarily intended for
numerical computations. It provides a convenient command line
interface for solving linear and nonlinear problems
numerically.
Octave can do arithmetic for real and complex scalars and matrices,
solve sets of nonlinear algebraic equations, integrate functions over
finite and infinite intervals, and integrate systems of ordinary
differential and differential-algebraic equations.
The Octave distribution includes a 200+ page Texinfo manual.
Two and three dimensional plotting is fully supported using gnuplot.
The underlying numerical solvers are currently standard
Fortran ones like Lapack, Linpack, Odepack, the Blas,
etc., packaged in a library of C++ classes.
===================================
q120.2. RLaB
http://rlab.sourceforge.net/ RLab
[author]:
Rlab is an interactive, interpreted scientific programming
environment. Rlab is a very high level language intended to provide
fast prototyping and program development, as well as easy
data-visualization, and processing.
Rlab is not a clone of languages such as those used by tools like
Matlab or Matrix_X/Xmath. However, as Rlab focuses on creating a good
experimental environment (or laboratory) in which to do matrix math,
it can be called "MATLAB-like" since the programming language
possesses similar operators and concepts.
===================================
q120.3. Scilab
http://www-rocq.inria.fr/scilab/ Scilab
[Dave Lindner]: Scilab is another good Matlab clone.
[author]:
Scilab is a matrix-based scientific software package
resembling Matlab-Simulink and Xmath-SystemBuild.
Scilab contains hundreds of built-in mathematical
functions, a rich set of data structures which includes
polynomials, rationals, linear systems, lists, sparse
matrices and comes with a number of specific toolboxes for
control, signal processing, ...
It features:
Elaborate data structures (polynomial, rational and string
matrices, lists, multivariable linear systems,...).
Sophisticated interpreter and programming language with
Matlab-like syntax.
Hundreds of built-in math functions (new primitives can easily be
added).
Stunning graphics (2d, 3d, animation).
Open structure (easy interfacing with Fortran and C via online
dynamic link).
Many built-in libraries :
* Linear Algebra (including sparse matrices, Kronecker
form, ordered Schur,...).
* Control (Classical, LQG, H-infinity, ...).
* Signal processing.
* Simulation (various ode's, dassl,...).
* Optimization (differentiable and non-differentiable, LQ solver).
* Metanet (network analysis and optimization).
Symbolic capabilities through Maple interface.
===================================
q120.4. Tela
http://www.geo.fmi.fi/prog/tela.html Tela
ftp://ftp.funet.fi/pub/sci/math/tela Tela via ftp
General NA package with graphics, linear algebra, FFT, etc.
Is this another Matlab clone?
[author]:
It is mainly targeted for prototyping large-scale
numerical simulations and doing pre- and postprocessing for them, and
it replaces a compiled language like C++ or Fortran in this respect.
The feature set is therefore biased to operations needed in partial
differential equation solvers.
===================================
q120.6. Medal
NOTE: this software seems to have disappeared!
If anyone knows how to get it, please contact me ... Steve.
References:
(1) Pang, G.K.H.,``Knowledge-based Control System Design'', in
Recent Advances in Computer-Aided Control Systems Engineering,
Jamshidi, M and Herget, C.J. (ed.), Elsevier Science Publishers, 1992.
(2) Pang, G.K.H., ``A Knowledge Environment for an Interactive Control
System Design Package'', Automatica, Vol. 28. No. 3, pp. 473-491, May 1992.
===================================
q120.7. Euler
ftp://am.ku-eichstaett.de/pub Euler via ftp
[author]:
EULER started as a MatLab clone. It is now a program, which can handle
real, complex and interval numbers and matrices, has a 2D/3D graphics, a
builtin modern programming language (extension of MatLab's), an exact
scalar product, and the Windows 95 version can call functions in an
external DLL. The OS/2 and Windows versions interact nicely with the GUI,
and have a notebook style interface.
The Unix version is free, the OS/2 version free for educational use, and
the Windows version cheap shareware.
These features make EULER an ideal tool for the tasks such as
* Inspecting and discussing functions of one real or complex
variable.
* Viewing surfaces in parameter representation.
* Linear algebra and eigenvalue computation.
* Testing numerical algorithms.
* Solving differential equations numerically.
* Computing polynomials.
===================================
q120.8. Prophet
http://www-prophet.bbn.com/ Prophet
ftp://www-prophet.bbn.com Prophet via ftp
email: prophet-info@bbn.com
[author]:
Prophet is an NIH-sponsored Unix workstation software package for life
science computing. Prophet includes tools for data management,
statistical analysis, curve fitting, data graphing, mathematical
modeling, and genetic sequence analysis.
One of PROPHET's greatest assets is its new graphical
user interface . Employing the latest advances in software
technology, PROPHET lets you store,
analyze and present Data Tables, Graphs, Statistical Analyses and
Mathematical Modeling, and Sequence Analyses with high-resolution
graphics and multiple windows. Anyone, from the computer-naive to the
computer-sophisticate, can learn to use it quickly and effectively.
PROPHET is a National Computing Resource for Life Science Research
sponsored by the National Center for Research Resources of the
National Institutes of Health.
Unfortunately, prophet is distributed in binary form only.
It is large: it takes something like 65 MB disk space.
===================================
q120.9. Yorick
http://wuarchive.wustl.edu/languages/yorick/yorick-ad.html Yorick
ftp://ftp-icf.llnl.gov/pub/Yorick/ Yorick ftp site
[author]
Yorick is an interpreted language. It has:
* A C-like language, but without declarative statements. Operations
between arrays require no explicit loops, which accounts for
Yorick's high speed. Scientific computing and numerical analysis
are the goals of most Yorick sessions.
* An X window system interactive graphics package.
* A library of functions written in the Yorick language.
Because Yorick can read either text or binary files, it can be used
"out of the box" as a pre- and post-processor for most existing
physics simulation programs.
As a pre-processor, you can write a Yorick program that produces
complicated input files for a simulation. These might be based on
output from other programs, or might require evaluation of complicated
functions or involve a lot of repetition.
As a post-processor, Yorick allows you to compare the results of
several simulations or to analyze results of a single simulation in
ways you did not foresee when you ran it.
===================================
q120.10. SpYorick
http://www.arrakis.es/~worm/ SpYorick
[author] SpYorick is a plug-in for Yorick that adds
support for sparse matrices, operations among matrices and vectors and
solution of systems of linear equations.
See iii q120.9, "Yorick".
===================================
q120.11. PETSc
http://www.mcs.anl.gov/petsc PETSc
[author]:
Portable, Extensible Toolkit for Scientific Computation (PETSc).
PETSc provides many tools for the parallel (and uniprocessor),
numerical solution of PDEs that require solving large-scale, sparse
nonlinear systems of equations. PETSc includes nonlinear and linear
equation solvers that employ a variety of Newton techniques and Krylov
subspace methods. In addition, PETSc provides several parallel sparse
matrix formats, including compressed row, block compressed row, and
PETSc is a set of parallel
software libraries for the implicit solution of PDEs and related
problems. New features include:
(1) a parallel, sparse, symmetric matrix storage format, this includes
support for sequential Cholesky and ICC(k)
(2) a complete framework for parallel linear multigrid on
structured grids (for both linear and nonlinear problems)
(3) Mandel's balancing Neumann-Neumann method for scalar PDEs
(4) an interface to the Tufo-Fischer highly efficient parallel
coarse grid direct solver library tfs
(5) support for managing "composite" vectors consisting of
subvectors that represent conceptually different quantities
(for example, constraints or Lagrange multipliers)
(6) more complete hypertext documentation, including links to
hypertext versions of all the examples and source code
===================================
q120.12. The Blitz++ Numerical Library Project
http://www.oonumerics.org/blitz/ Blitz++
[author]:
Blitz++ is a C++ template class library for scientific computing.
It offers a high level of abstraction, but performance which appears
to be rivalling that of Fortran. The current alpha version supports arrays
and vectors. Matrices are only partially implemented and undocumented;
use at your own peril.
===================================
q120.13. Ascend
http://www-2.cs.cmu.edu/~ascend Ascend at CMU
[author]:
ASCEND IV is a free, large-scale, equation-based, environment
featuring a strongly-typed, object-oriented model-description
language. ASCEND is designed to reduce the time needed for
creating, debugging, and solving mathematical models by orders of
magnitude in comparison with C++-like and FORTRAN-like languages.
ASCEND includes interactive support tools for modeling, debugging, and solving
systems with tens of thousands of nonlinear algebraic or
differential equations. Including:
- a library of equilibrium-based unit operations for chemical
engineering and an easily extensible physical properties
library with thirty-four common species.
- user-centered structured methodology for reaching correct
problem specifications.
- automatic analysis of degrees of freedom.
- automatic checking of unit conversions on input data and
equations.
- automatic initialization of variables.
- choice of automatic scaling methods for nonlinear equations.
- an object-oriented modeling language.
- GNU Licensed source code for all distributed system
components.
===================================
q120.14. Algae, formerly called Alki
http://www.eskimo.com/~ksh/algae/index.html Algae home page
[author]:
Welcome to the home of Algae, a high-level interpreted language
for numerical analysis. Algae borrows from languages like MATLAB and
APL, but it was developed because we needed a free, efficient,
and versatile language capable of handling large problems.
Algae is fast. It's generally faster than MATLAB, RLaB, and Octave,
often by a significant margin. Of course, words like "generally"
and "often" (and benchmarks themselves, for that matter) don't mean
much when it comes time to run your particular problem, and I'm
sure that you can find cases where Algae gets beat. Still, Algae is fast.
Algae's arrays may be stored in sparse form; only the non-zero elements
and their locations are stored. This type of storage is required
for practical analysis in many fields. In my own field (structural
dynamics), a matrix with 20,000 rows and columns is not considered large.
===========================================================================
q125. Commercial NA Libraries and Packages
Commercial libraries and packages tend to merge, so I've combined
them in one category. Typically a commercial product contains:
* a library of numerical routines
* graphics routines
* an interactive interpreted language
Many symbolic algebra packages also contain NA packages.
For info on these packages, see iii q520, "Symbolic Algebra".
An good article on commercial software is:
Braham, Robert. "Math & Visualization: new tools, new frontiers",
IEEE Spectrum 32, 11 (November 1995), p. 19-36.
The article contains tables comparing large number of commercial products.
There is no mention of the many excellent free products though.
* iii q125.1, "NAG"
* iii q125.2, "IMSL and PV-WAVE"
* iii q125.3, "Matlab and Simulink"
* iii q125.4, "WavBox"
* iii q125.5, "CraySoft Libraries"
* iii q125.6, "IDL"
* iii q125.7, "Comparison of IDL and Matlab"
* iii q125.8, "Mlab"
* iii q125.9, "Gauss"
* iii q125.10, "MathViews"
* iii q125.11, "Matcom: Matlab to C++ Compiler"
* iii q125.12, "O-Matrix"
* iii q125.13, "UCALC"
* iii q125.14, "Laipe"
* iii q125.15, "VisualMath"
* iii q125.16, "Harwell Subroutine Library"
* iii q125.17, "Ch Interpretor for C++ numerics"
===================================
q125.1. NAG
http://www.nag.co.uk NAG in England
http://www.nag.com/ NAG in USA
[SJS]: Numerical, symbolic, statistical, and visualization libraries in
Fortran 77, Fortran 90, C, Pascal, Ada, and parallel machine versions.
High performance Fortran 90 and Fortran 77 compilers.
NAG Ltd (The Numerical Algorithms Group)
Wilkinson House
Jordan Hill Road
OXFORD
OX2 8DR
UK
Tel: +44 1865 511245
NAG Inc
1400 Opus Place
Suite 200
Downers Grove
IL 60515-5702
USA
Tel: +1 708 971 2337
===================================
q125.2. IMSL and PV-WAVE
http://www.vni.com Visual Numerics, Inc.
[SJS]: IMSL is a set of routines in C, C++, and Fortran
libraries for general NA, statistics and graphics.
PV-WAVE is a visual programming environment that includes IMSL
as a "plug-in".
Visual Numerics, Inc.
IMSL and Stanford Graphics Products
9990 Richmond Avenue, suite 400
Houston, Texas 77042-4548
USA
Tel: 800-222-4675
Tel: 713-784-3131
FAX: 713-781-9260
e-mail: marketing@houston.vni.com
Visual Numerics, Inc
PV-WAVE Products Division
6230 Lookout Road
Boulder, Colorado 80301
USA
Tel: 800-447-7147
Tel: 303-530-9000
FAX: 303-530-9329
info@boulder.vni.com
[author]:
* Comprehensive Mathematical Functionality
* integration and differentiation
* transforms
* differential equations
* linear systems
* interpolation and approximation
* eigensystem analysis
* optimization
* special functions
* basic matrix/vector operations
* nonlinear equations
* utilities
* Extensive Statistical Functionality
* basic statistics
* tests of goodness-of-fit
* time series analysis and forecasting
* analysis of variance
* regression
* nonparametric statistics
* correlation
* random number generation
* cluster analysis
* categorical and discrete data analysis
* probability distribution functions and inverses
* factor analysis
* utilities
* Exponent Graphics includes:
* Presentation quality graphs for application development
* Application program interface provides easy access to either
FORTRAN or C
* Two function calls can automatically produce one of over 30
different plot types.
* Maximum flexibility for modifying plot characteristics
* Powerful interactive editing and customization tools
* CGM, PostScript, HPGL and other device drivers
* Support for popular graphics accelerators and output systems
* Full Windows-based online documentation with hypertext links
PV-WAVE is a software environment for solving problems requiring the
application of graphics, mathematics, numerics and statistics to data
and equations.
PV-WAVE uses an intuitive fourth generation language (4GL) that
analyzes and displays data as you enter commands. With it you can
perform complex analysis, visualization, and application
development quickly and interactively.
Robust integrated graphics, numerics, data I/O, and data management
has made PV-WAVE the number one selling Visual Data Analysis software
family.
PV-WAVE and the IMSL numerical and statistical routines, which are
seamlessly integrated in PV-WAVE Advantage, are being used by more
than 300,000 technical professionals on workstations worldwide.
===================================
q125.3. Matlab and Simulink
http://www.mathworks.com/ Mathworks
The MathWorks, Inc.
24 Prime Park Way
Natick, MA 01760-1500
(508) 653-1415
For a comparison of Matlab and IDL, see
iii q125.7, "Comparison of IDL and Matlab".
[SJS]: Matlab is an interactive general NA package, including graphics.
A huge variety of "toolboxes" are available, both from the
vendor and on the net, for various specialized NA areas:
control systems, neural nets, optimization, symbolic math,
and on and on.
Simulink is modeling, simulation, and system analysis tool.
[author]:
MATLAB is a technical computing environment for high-performance
numeric computation and visualization. MATLAB integrates numerical
analysis, matrix computation, signal processing, and graphics in an
easy-to-use environment where problems and solutions are expressed
just as they are written mathematically - without traditional
programming.
MATLAB has evolved over a period of years with input from many users.
In university environments, it has become the standard instructional
tool for introductory courses in applied linear algebra, as well as
advanced courses in other areas. In industrial settings, MATLAB is
used for research and to solve practical engineering and mathematical
problems. Typical uses include general purpose numeric computation,
algorithm prototyping, and special purpose problem solving with matrix
formulations that arise in disciplines such as automatic control
theory, statistics, and digital signal processing (time-series
analysis).
MATLAB also features a family of application-specific solutions that
we call toolboxes. Very important to most users of MATLAB, toolboxes
are comprehensive collections of MATLAB functions (M-files) that
extend the MATLAB environment in order to solve particular classes of
problems. Areas in which toolboxes are available include signal
processing, control systems design, dynamic systems simulation,
systems identification, neural networks, and others.
SIMULINK is a tool for modeling, analyzing, and simulating an
extraordinarily wide variety of physical and mathematical systems,
including those with nonlinear elements and those which make use of
continuous and discrete time.
As an extension of MATLAB, SIMULINK adds many features specific to
dynamic systems while retaining all of MATLAB's general purpose
functionality.
Using SIMULINK, you model a system graphically, sidestepping much of
the nuisance associated with conventional programming.
===================================
q125.4. WavBox
http://www.wavbox.com/ Wavbox
email: info@wavbox.com
A wavelet Toolbox for Matlab.
[author]:
A software toolbox for wavelet transforms and adaptive
wavelet packet decompositions with new search algorithms.
Requires Matlab.
===================================
q125.5. CraySoft Libraries
http://www.cray.com/PUBLIC/product-info/craysoft/CS_home_txt.html Cray product info
http://www.cray.com/ Cray main
http://www.cray.com/craysoft/ Craysoft main
email: crayinfo@cray.com
Corporate Headquarters:
Cray Research, Inc.
655 Lone Oak Drive
Eagan, Minnesota 55121
(800) 289-2729 or (612) 683-3030,
[author]
Fortran 90 compilers and NA library for Cray, Sparc,
Macintosh, and Windows environments.
* Seismic migration
* Structural analysis
* Financial modeling
* Decision support analysis
* General scientific
* Computational chemistry
* Computational physics
* Intelligence, signal and image processing
* Electronic simulation
===================================
q125.6. IDL
Research Systems Inc.
http://www.rsinc.com/ Research Systems, Inc.
Research Systems, Inc.
2995 Wilderness Place
Boulder, CO 80301 USA
Phone: 303-786-9900
email: info@rsinc.com
For a comparison of IDL and Matlab, see
iii q125.7, "Comparison of IDL and Matlab".
IDL binaries are available at:
ftp://ftp.rsinc.com/pub/idl Research Systems, Inc.
ftp://boulder.colorado.edu/pub/idl U. of Colorado
Following are two sets of comments on IDL:
1. By Pierre Maxted
2. By Amara Graps
================
1. Comments by Pierre Maxted
I find that IDL is good for "playing" with data. This works well for
astronomers who seem to end up always wanting to do something a little
different to last time to data that always has slightly different quirks
every time. I also find that it is a rather easy language in which to
write my own routines. This is probably because I can start with
interactive IDL to get the feel for what the data is like and what I want
to do with it - this then becomes a simple batch file which can be turned
into a routine if the procedure is useful - this seems to be a natural
way to develop things. These libraries of routines are what makes IDL
really powerful in my opinion. I found that adding the astronomy user's
library to IDL was like adding wheels to a car. I would recommend to
anyone considering using IDL to find out what libraries are out
there (e.g. starting at the IDL WWW home page).
Whatever you add to the FAQ, make one point clear - calling IDL a fancy
plotting package is like calling a Formula 1 racing car good for picking
up the kids from school - IDL can do plotting, but that is not its
strength.
Well, I agree that the hard copy manuals are rather opaque but Version 4
of IDL has online help (Hyperhelp) that is rather good - especially since
it had text searching capabilities so that you can go straight to the bit
you need (usually).
================
2. Comments by Amara Graps
Following is an excerpt of comments by [Amara Graps]:
For the full text of her review, please see:
http://www.amara.com/papers/miscpap.html Amara Graps' Papers
ftp://ftp.amara.com/papers/IDL_Matlab.txt Amara Graps' Papers via ftp
If you install IDL without a valid license, you will get IDL's
7 minute demo mode. This mode is designed for users who are
considering buying the package.
IDL is a vector-based language that makes it easy to manipulate arrays
and matrices. I've done testing comparing IDL speed to
Fortran in various actions, and IDL was as fast as a Fortran program for
the IDL array computations where loops were removed (i.e., when
using implicit loops in IDL instead of explicit FOR statements).
The scientific functions and procedures that come with IDL are often all
that scientists need. In addition, there are net archives
containing contributed routines. The archives at
John Hopkins and at Goddard are especially good (see below).
The language, for the most part is "open", i.e. you can see the
text of any particular procedure or function, in case you doubt the
technique, or want to modify it. Some functions and procedures are
black-box, intrinsic functions or procedures, but not nearly as many as
Matlab (see below) are.
Most work in IDL is done at the command line level. However, IDL supplies
rudimentary "widgets" to wrap a GUI around your procedures and
functions. You can create buttons, menus, scrollboxes etc.
Three-d plotting is currently not very well documented, and the way that
IDL does it is very convoluted. Other users and I have complained about
it, and I think RSI are taking steps to better document how to do it.
Image processing and animation is pretty slick.
If you need to do "slicing and dicing" of a volume, in a way like
Spyglass Dicer, IDL has a really great widget routine to do it.
The IDL plots are high quality enough to use in initial journal
submissions.
RSI's support (writing to support@rsinc.com) is pretty good, I
usually get responses within 24-34 hours. You have to pay yearly technical
support costs, though- about $200 year (don't remember exactly how much).
The Usenet group: comp.lang.idl-pvwave has some smart programmers giving
answers if you don't want to pay for the IDL technical support. RSI
usually doesn't answer questions on that newsgroup (they have a company
policy against promoting IDL there because it's shared by two products:
IDL and PV-WAVE).
I've never liked the IDL documentation very much. The information that you
need probably *is* in the manuals, but it's somewhat hard to find (the
manuals are organized in a weird way). [Note, however, the comments
by Pierre Maxted above].
The anonymous ftp sites below contain public domain IDL code.
http://fermi.jhuapl.edu/www/s1r/idl/idl.html JHU/APL/S1R IDL library
ftp://fermi.jhuapl.edu/pub/idl JHU/APL/S1R IDL library via ftp
NASA IDL Astronomy User's Library, run by Wayne Landsman:
http://idlastro.gsfc.nasa.gov/homepage.html NASA IDL Astro Library
ftp://idlastro.gsfc.nasa.gov/pub NASA IDL Astro Library via ftp
ftp://iuesn1.gsfc.nasa.gov IUE RDAF library at NASA
ftp://cetus.colorado.edu/pub IUE RDAF library at U. of Colorado
ftp://ftp.astro.psu.edu/pub/nefftp/icur ICUR Spectral Analysis Software
ftp://legacy.gsfc.nasa.gov/rosat/software/idl IDL ROSAT software
ftp://ftp.sma.ch/pub/idlmeteo IDLmeteo library
ftp://eos.crseo.ucsb.edu/pub/idl ESRG library
Hal Mueller has a Digital U.S. Map browser based on images
created by Ray Sterner at Johns Hopkins University using IDL:
http://www.zilker.net/~hal/apl-us// Map browser
===================================
q125.7. Comparison of IDL and Matlab
Following is an excerpt of a paper by [Amara Graps]:
For the full text of her review, please see:
http://www.amara.com/papers/miscpap.html Amara Graps' Paper
ftp://ftp.amara.com/papers/IDL_Matlab.txt Amara Graps' Paper via ftp
IDL is a package that began life as an image-processing utility that has
grown to be a general-purpose numerical analysis tool. Matlab started as
a numerical analysis package that now includes [at extra cost] image
processing tools. Now the two have a similar scientific data-analysis
environment, with capabililties to build GUI programs and do very robust
data analysis.
(Note: all prices are approximate October 1995 prices - SJS)
They each cost about the same: ~$1500 for Mac and PC versions and more for
Unix (~4000 -- single user to $15,000 -- unlimited number of users).
Matlab is popular among education institutions because it has exceptional
educational discounts. If you are an academic, Matlab can be had for
$495 and each toolbox only $195. My NASA colleagues thought that
MathWorks "nickled- and-dimed" them with the costs of the Toolkits (like
the signal processing toolkit), but given what you get, it probably
isn't that unreasonable.
IDL seems to be more widespread in the NASA communities probably because
the original developer used several spacecraft teams (Pioneer Venus and
Voyager) as test beds for the IDL software.
IDL is more of a true programming language. Matlab has scripts and
functions and no way to explicitly type a variable. IDL has programs,
procedures, and functions and a language syntax sort of like a cross
between Fortran, Pascal, and APL. If you have programmed in Fortran
before, then the syntax will be a snap to learn. Matlab's syntax is much
more compact than IDL's. For example: x = transpose(y) in IDL is x=y' in
Matlab.
Matlab has many more built-in, intrinsic functions than IDL.
MatLab has many optional Toolkits, such as a Signal Processing
Toolkit and an Image Processing Toolkit, which are libraries
of more intrinsic functions.
Reading and writing files, and handling formats such as GIF,
PICT, GDF, and custom formats, seems much easier in IDL than MATLAB.
Handling directories is difficult in MATLAB when run on non-unix
machines.
Matlab has more types of graph types than IDL, and handling
colors is simpler than IDL. However, I found most
other Matlab graphical programming non-intuitive. It uses a system where
each element in a graph is an "object." These objects can have
sub-objects. So to change an element in a graph, say the axis color, you
have to first find the object (a "get" function), and then set it to the
color you want. IDL has system variables storing all graphics elements
which can be easily changed. One can also customize a graph upon making
the graph, with a keyword.
IDL's technical support is pretty good, but Matlab's is better. Post
a question on comp.soft-sys.matlab and either a developer, the company
president, or a tech support person will respond that day. You can call
them, too, but it's not a toll-free call.
===================================
q125.8. Mlab
http://www.civilized.com/MLAB.htmld/ Civilized Software
Civilized Software, Inc.
8120 Woodmont Ave., Ste. 250
Bethesda, MD 20814
U.S.A.
1-301-656-4714
1-301-656-1069 fax
Email: csi@civilized.com
[author]:
MLAB, (for Modeling LABoratory), is a program for interactive
mathematical and statistical modeling. MLAB was originally developed
at the National Institutes of Health. It includes curve-fitting,
differential equations, statistics and graphics as some of its major
capabilities.
===================================
q125.9. Gauss
http://www.econotron.com Econotron Software
Aptech Systems, Inc., Tel: (206) 432-7855, Fax: (206) 432-7832
23804 South East Kent-Kangley Road
Maple Valley, WA 98038 USA
(206) 432-7855
[author]:
The GAUSS Mathematical and Statistical System is available for IBM PCs and
compatibles as well as UNIX workstations
As a complete programming language, the GAUSS system is both
flexible and powerful. Immediately available to the GAUSS user is a wide
variety of statistical, mathematical and matrix handling routines. Powerful
data handling capabilities including a data loop allow transformations in a
data set by directly using variable names in expressions. This greatly
simplifies data transformations and makes for shorter more readable programs.
GAUSS can be used in either command mode(interactively) or in edit mode. In
command mode; one-line commands, or small screen-resident programs, can be
issued and the results of calculations seen immediately. In edit mode you
can write complex programs and store them in files.
GAUSS has over 400 functions built in, including LINPACK and EISPACK
routines.
===================================
q125.10. MathViews
http://www.mathwizards.com MathViews
[author] MathViews for Windows is matlab look-alike. It
has a full set of linear algebra and signal processing
functionality. It provides easy access to: matrix and linear
algebra, digital signal processing, instrument control, image
processing, time series analysis, data visualization and
waveform display and editing.
MathViews is highly compatible with the matlab syntax and will
execute most matlab m-files with no changes.
We also have WaveTool.
WaveTool is an interactive software tool for creating, editing
and analyzing captured waveshapes. Waveforms can be created
using any combination of drawing, math expressions (matlab
syntax), insertion from a library of waveforms or data values
pasted from other applications such as Microsoft Excel.
===================================
q125.11. Matlab to C++ Compiler and C++ Matrix Class Library
http://www.mathtools.com Mathtools
or email: info@mathtools.com
[author]:
MATCOM V2 is a Matlab(R) to C++ compiler. MATCOM creates MEX files
and standalone C++ applications, with royalty free distribution.
MATCOM translates Matlab code to C++, which is compiled by your
optimizing C++ compiler. The resulting code runs significantly faster
than the original interpreted source.
Prior knowledge of C++ is not necessary to use MATCOM. The compilation
is fully automated by a smart project manager.
Fully functional, time limited evaluation version of MATCOM V2 can be
downloaded freely from the MathTools web site.
MAT, a Matlab Compatible C++ Matrix Class Library,
is designed for development of advanced
scientific high-level C++ code. Evalution version of the MAT
can be downloaded from the home page noted above.
The library includes Complex math, Binary and unary operators,
Powerful indexing capabilities, Signal processing, File I/O, Linear
algebra, String operations and Graphics. Over 300 mathematical
functions are included in MAT.
MAT supports matrices of doubles, floats, ints and chars
mixed in the program. Images can be stored in matrices of chars,
using 1/8 memory storage. On many applications, where 8 digits of
precision are sufficient, float-precision matrices can save half
the memory usage. Memory allocation and de-allocation is managed
automatically.
===================================
q125.12. O-Matrix
http://www.omatrix.com Harmonic Software
O-Matrix For Windows:
[author]:
O-Matrix is a complete solution for analysis, visualization, and
rapid application development, (RAD). The interactive environment
enables both point-and-shoot oriented analysis for rapid solutions
and a powerful language and debugger for large demanding applications.
The integrated matrix language provides performance that far exceeds
typical integrated environments and often rivals compiled code for
numerically-intensive applications.
SPT - The Signal Processing Toolbox for O-Matrix:
SPT for O-Matrix provides a broad, extensible
set of functions and utilities that expands the capabilities of
O-Matrix in the area of digital signal processing. Built on the
high-performance capabilities and flexibility of O-Matrix, the toolbox
contains tools for algorithm development, data analysis, and visual
presentation. SPT enables the rapid development of robust, high-performance
applications in areas including digital filtering, spectral estimation,
digital communication system simulation, time series analysis, real time
control, geophysics, and more. The package comes with complete source code,
online tutorials and examples, and unlimited free technical support.
KBF - The Kalman Filter Interface Pack for O-Matrix:
The KBF interface simplifies the design of a filter
or smoother by dividing the design process into simple steps with each
step corresponding to an input window or dialog. Extensive plotting of
results, including residuals and correlations is also automated. In
addition, a simulation feature is included to aid in testing the validity
of the design. KBF is used in a wide range of applications such as tracking,
weather and earth process modeling, economic forecasting and bioengineering.
Harmonic Software Inc.
800-895-4546 / 206-367-8742
===================================
q125.13. UCALC
http://www.ucalc.com UCALC for Windows
[author]:
UCALC includes many features useful for scientific calculations
and graphing:
* Scientific Expression Evaluator
* Eq graphing: Cartesian, polar, 3D, parametric, data files
* Equation Solver
* Numerical Integrator
* Many scientific functions
* Supports user functions and variables
* Built-in and user-defined numeric formats
* Unit Converter
* Summation Tables
* Financial Modules
* General Ledger
In addition to the above, UCALC introduces an innovative feature
- User Solution Modules (USM). USMs are created by simply providing
a math formula, and giving it a name. UCALC parses the formula and
creates a template form which allows the user to solve for any item
by simply filling in the blanks. Useful USMs are included to get
you started.
===================================
q125.14. Laipe
http://www.equation.com/laipe/laipe.htm Laipe
[author]: Fast parallel solvers for Windows NT running on
an SMP computer. Manual includes:
1.Introduction to LAIPE
2.Constant Bandwidth, Symmetric, and, Positive Definite
Systems
3.Variable Bandwidth, Symmetric, and Positive Definite
Systems
4.Dense, Symmetric, and Positive Definite Systems
5.Constant Bandwidth and Symmetric Systems
6.Variable Bandwidth And Symmetric Systems
7.Dense And Symmetric Systems
8.Constant Bandwidth And Asymmetric Systems
9.Variable Bandwidth And Asymmetric Systems
10.Dense and Asymmetric Systems
11.Constant Bandwidth And Asymmetric Solvers with
Partial Pivoting
12.Constant Bandwidth, Symmetric, and Positive Definite
Solvers with Partial Pivoting
13.Constant Bandwidth and Symmetric Solvers with Partial
Pivoting
14.Dense and Asymmetric Solvers with Partial Pivoting
15.Dense and Asymmetric Solvers with Full Pivoting
16.Auxiliary Subroutines for Employing Processors
===================================
q125.15. VisualMath
http://www.drhuang.com VisualMath, DrMath
[author, Weiguang Huang]:
It is an online symbolic math and computer algebra system.
It can perform exact, numeric, symbolic and graphic computation,
e.g. arbitrary-precision calculation, solve equation, plot data and
user-defined functions, linear regression, symbolic differentation
and integration, pattern-match. It is a programming language, in
which you can define conditional, case, piecewise, recursive,
multi-value functions and procedures, derivatives, integrals
and rules.
It runs in any computer that supports Java.
===================================
q125.16. Harwell Subroutine Library
http://www.software.aeat.com/hsl2000/ HSL 2000
[author]:
HSL 2000 contains codes for Automatic differentiation, Differential Equations, Eigenvalues and Eigenvectors, Mathematical Functions, Sorting, Linear Programming, Linear Algebra, Nonlinear Equations, Polynomials, Optimization and Non-linear data fitting. It contains many new routines, which have been developed as a result of recent research into advanced numerical algorithms.
===================================
q125.17. Ch Interpretor for C++ numerics
http://www.softintegration.com/ Ch
[author]:
Ch is a superset of C interpreter. It is embeddable. C/Ch/C++ allows software developers to use one language, anywhere and everywhere, for any programming and numerical computing tasks.
By incorporating external libraries, it provides access to linear algebra, ODE, integration, graphics, etc.
===========================================================================
q135. Newsgroups for NA
Newsgroups related to numerical analysis are:
sci.math.num-analysis The primary group for NA issues.
sci.math.symbolic Covers symbolic algebra: Mathematica, Maple, Macsyma, Derive, Reduce, Mcad, etc.
comp.soft-sys.math.mathematica Devoted to Mathematica.
sci.op-research Covers operations research, linear programming, non-linear programming.
sci.stat.math Covers probability and statistics.
sci.math Covers a broad range of mathematical subjects, at levels from trivial to advanced.
sci.math.research Covers advanced mathematics, and is generally theoretical as opposed to applied.
===========================================================================
q140. Professional Societies for NA
* iii q140.1, "The (AMS) American Mathematical Society"
* iii q140.2, "(SIAM) The Society for Industrial and Applied Mathematics"
* iii q140.3, "ACM, Inc. (Association for Computing Machinery)"
* iii q140.4, "IEEE The Institute of Electrical and Electronic Engineers"
===================================
q140.1. The (AMS) American Mathematical Society
http://www.ams.org/ AMS
email: ams@math.ams.org
General organization information, preprint titles, pointers to
other preprint servers and net resources. Also includes:
MathDoc, the document delivery service offered by the AMS, provides
copies of original journal, collection and conference proceedings
articles from publications covered by Mathematical Reviews, Current
Mathematical Publications, and the MathSci database. This costs
roughly US$14. per ten pages, as of October 1995.
MathSciNet is a searchable database available on the World Wide Web.
It is based on the data in Mathematical Reviews and Current
Mathematical Publications, leading publications that catalog and
review research literature in mathematics. This costs roughly
US$5500. per year, as of October 1995.
===================================
q140.2. (SIAM) The Society for Industrial and Applied Mathematics
http://www.siam.org/ SIAM
email: siam@siam.org
General organizational information, tables of contents
of SIAM journals, and recently accepted articles.
Society for Industrial and Applied Mathematics
3600 University City Science Center
Philadelphia, PA 19104-2688
(215) 382-9800
Journals include:
SIAM Scientific Computing
SIAM Matrix Analysis
SIAM Control and Optimization
===================================
q140.3. ACM, Inc. (Association for Computing Machinery)
http://www.acm.org/ ACM
email: ACMHELP@acm.org
General organizational information, info on journals and conferences.
Of particular interest are:
Transactions on Mathematical Software (TOMS)
http://www.acm.org/toms/ ACM TOMS
Collected Algorithms of the ACM (CALGO)
Software can be found in netlib (toms directory); see iii q115.1, "Netlib".
ACM Headquarters
One Astor Plaza
1515 Broadway
New York, New York 10036
212-869-7440
===================================
q140.4. IEEE The Institute of Electrical and Electronic Engineers
http://www.ieee.org IEEE
email: member.services@ieee.org
General organizational information, journals, books, conferences.
Tel: (800) 678-IEEE
Tel: (212) 705-7900
===========================================================================
q145. Electronic Newsletters for NA
http://www.netlib.org/na-net/na_home.html NA-Net
http://www.netlib.org/na-digest/topics NA-Net Index
email: nanet@na-net.stanford.edu
[author]:
The NA-Net is a system developed to serve the community of numerical
analysts and other researchers. The Na-Net provides two independent
databases and a weekly digest to its members. The Email Database is
the electronic mail address of each of its members, and is capable
of forwarding mail to them. In addition, this database serves as the
distribution list for the NA Digest (see below). The White Pages
Database is basically a directory service. It provides a way to
exchange personal information among its members. Contained in the
database are phone numbers, postal mailing addresses, research
interests, affiliations, etc. The NA Digest is a way to provide its
members with a weekly collection of articles on topics related
to numerical analysis and those who practice it. To get on the
mailing list for the digest and enter yourself in their database,
you can use email or the World Wide Web. Take advantage of this very
useful service!
===========================================================================
q150. Electronic Journals for NA
Indices of Journals
See the large list of online journals, and other resources,
at Penn State's Mathematics web site.
http://www.math.psu.edu/MathLists/Contents.html Penn State Mathematics
See also:
http://rattler.cameron.edu/swjpam/ The Southwest Journal of Pure and Applied Mathematics
===================================
BIT
http://math.liu.se/BIT/ BIT
BIT emphasizes numerical methods in approximation, linear algebra, and
ordinary and partial differential equations, but also publishes papers
in areas such as numerical functional analysis and numerical
optimization.
===================================
ETNA (Electronic Transactions in Numerical Analysis).
http://etna.mcs.kent.edu/ ETNA
An online peer reviewed journal. Keyword searching.
Most documents are postscript and may be downloaded.
Started in 1993. Indexes only itself.
===================================
EJDE, The Electronic Journal of Differential Equations
http://ejde.math.swt.edu/ EJDE
A purely on-line peer-reviewed journal.
===================================
The Electronic Journal of Linear Algebra
http://www.math.technion.ac.il/iic/ela/ Electronic J. of Linear Algebra
===================================
New York Journal of Mathematics
http://nyjm.albany.edu:8000/nyjm.html NY J. of Mathematics
Appears more abstract than applied. Started in 1994. Indexes only itself.
===========================================================================
q155. Online Papers for NA
General
See the listings for professional societies, especially the AMS,
in iii q140, "Professional Societies for NA".
Springer-Verlag
Preprints: See the Springer-Verlag preprint service via email.
Not free.
http://www.springer.de/server/services.html Springer Verlag
Virtual Library Math Journals Preprints
http://euclid.math.fsu.edu/Science/Preprints.html Virtual Lib Math Jnls Preprints
Links to numerous organizations offering preprints.
Networked Computer Science Technical Reference Library
http://www.ncstrl.org NCSTRL CoRR
A partnership of ACM, the Los Alamos e-Print archive,
and NCSTRL (Networked Computer Science
Technical Reference Library), an online Computing Research Repository
(CoRR) is being established. The Repository has been integrated into
the collection of over 20,000 computer science research reports and
other material available.
===========================================================================
q160. Miscellaneous Web Sites for NA
See also:
* iii q160.1, "C++ Resources for NA"
* iii q160.2, "Fortran Resources for NA"
* iii q160.3, "Math FAQ"
* iii q160.4, "Math Dictionaries and Glossaries"
* iii q160.5, "Eric Weisstein's World of Mathematics"
Caltech guide to mathematics resources
http://www.acm.caltech.edu/resources.html Caltech Guide to Math Resources
Good collection of pointers to quality sites.
Penn State's Math Guide
http://www.math.psu.edu/MathLists/Contents.html Penn State Mathematics
Huge site with information on many fields within mathematics.
U. C. Berkeley
http://www.math.berkeley.edu/ U.C. Berkeley
Berkeley's site includes courseware, pointers
to inet libraries, lecture notes, seminars, and software.
The World-Wide Web Virtual Library: Mathematics
http://euclid.math.fsu.edu/Science/math.html Virtual Lib: Mathematics
Specialized fields (topology, cryptography, optimization, etc),
academic departments, miscellaneous math societies and institutes,
pointers to commercial software, newsgroups, nice collection
of preprints pointers, electronic journals
U. Tennessee Knoxville Mathematics Archives WWW Server
http://archives.math.utk.edu/ U. Tenn Knoxville Math Archives
Mathematical Constants, by Steven Finch
http://pauillac.inria.fr/algo/bsolve/constant/constant.html Constants
Constants and algorithms for their generation.
The reclusive Dr. TP's list of www sites for numerical methods
http://tonic.physics.sunysb.edu/docs/num_meth.html Dr. TP's NA page, USA
http://zar.unizar.es/www/num_meth.html Dr. TP's NA page, Spain
http://www.labyrinth.net.au/~ctrans/tomasz.html Dr. TP's NA page, Australia
Amara Graps' list of science links
http://www.amara.com/science/science.html Amara Graps' list
A Catalog of Mathematics Resources on WWW and the Internet
http://mthwww.uwc.edu/wwwmahes/files/math01.html Catalog of Math Resources
By M. Maheswaran, University of Wisconsin Marathon Center.
Another large site, with a sizeable section on Applied Mathematics.
Alan Miller's Page:
http://members.ozemail.com.au/~milleraj/ Alan Miller
A collection of code for least squares, random number generation,
quadruple precision, and for various statistical purposes.
All of this code is written in Fortran 90 and most of it is in the
subset of Fortran 90 chosen for the free ELF90 compiler.
Altug Koker's list of simulation software
http://piranha.eng.buffalo.edu/simulation/comp.simulation/FAQ.html Simulation Software
(See his Q15.). Contains pointers to software for:
aerospace, automotive, chemistry / biotechnology, graphics and imaging,
electronics / electrical engineering, petroleum
The Yahoo server's index of Mathematics topics.
http://dir.yahoo.com/Science/mathematics Yahoo's Math index
Includes commercial products, conferences, journals, and various
subfields of mathematics, primarily in applied mathematics.
Scientific Applications on Linux Web Page
http://sal.kachinatech.com/ Scientific Apps on Linux
Contents:
* Commercial Scientific Software
* MatLab Alike and Related Packages
* Mathematics and Statistics
* Finite or Boundary Element
* Numerical Analysis
* Signal, Communication, Data and Image Processing/Visualization
* CAD, Graph, Drawing and Modelling Tools
* Scientific Data Plotting Packages
* Scientific Data Plotting Libraries
* General Purpose Graphic Libraries
* Word Processing, Typesetting And Office Software
* X-Window GUI Construction
* Misc Scientific Packages or Libraries and Links
* Other Links
For a wide variety of links to mathematical and scientific software, see:
http://stommel.tamu.edu/~baum/linux-meta.html S. Baum's site
Mathematical Modeling web pages
http://www.mcs.anl.gov/mathmodeling ANL
===================================
q160.1. C++ Resources for NA
Indices:
Trumphurst FAQ on C++ Libraries
http://www.trumphurst.com/cpplibs1.html Trumphurst
The Object-Oriented Numerics Page
http://oonumerics.org/oon/ Object-Oriented NA
Pointers to C++ libraries and classes.
The Blitz++ Numerical Library Project
See iii q590, "The Blitz++ Numerical Library Project"
Also see iii q590, "Skip Carter's Home Page".
Also see Roldan Pozo's page:
http://math.nist.gov/~RPozo/index.html Pozo's page
Individual Libraries:
For a collection of routines in C in Netlib (See iii q115.1, "Netlib"):
clapack (numerical linear algebra)
cephes (special functions, minimization, other stuff)
meschach (sparse linear systems and others)
Also see Joerg Arndt's web page on FFT code, at
iii q240, "Transforms (FFT, etc) and digital signal processing (DSP)"
===================================
q160.2. Fortran Resources for NA
http://www.fortranlib.com The Fortran Library
[author]:
The Fortran Library is a comprehensive guide
to online Fortran resources, including compiler vendors and
resellers, benchmarks, programming tools, books and articles on Fortran
and numerical methods, and commerical and public domain Fortran software.
http://www.fortran.com/fortran/ The Fortran Market
[author]:
The Fortran Market also provides
many links to Fortran resources and is a reseller for several Fortran 90
and 95 compilers, benchmarking and test suites, and books on Fortran.
===================================
q160.3. Math FAQ
The sci.math FAQ by Alex Lopez-Ortiz is a good reference for
many mathematical questions. It is more oriented towards
pure mathematics than NA.
http://daisy.uwaterloo.ca/~alopez-o/math-faq/math-faq.html Alex Lopez-Ortiz's list
ftp://rtfm.mit.edu/pub/usenet-by-group/news.answers/sci-math-faq/ Alex Lopez-Ortiz's list via ftp
===================================
q160.4. Math Dictionaries and Glossaries
Mathematical Programming Glossary:
http://www.cudenver.edu/~hgreenbe/glossary/glossary.html Glossary
===================================
q160.5. Eric Weisstein's World of Mathematics
http://mathworld.wolfram.com Weisstein's World of Mathematics
Eric Weisstein's World of Mathematics, developed
with the support of Wolfram Research, is one of the web's
most extensive mathematics resources.
===========================================================================
q165. Books, With and Without Software, for NA
See also specific subject areas in this FAQ
at iii q800, "NA FAQ: Table of Contents".
For an on-line mathematics dictionary, see:
iii q160.4, "Math Dictionary".
Acton, Forman S. 1990
Numerical methods that [usually] work
Harper & Row, Publishers
ISBN 0883854503.
[Daniel Pick] This book is almost worth its price just for the cathartic
interlude in the middle of the book on what not to compute. You should
require your students to read it, learn it, live it. You may find just
giving them the railroad problem found at the beginning of the book a
worthwhile exercise. [Bill Frensley] Amen, brother! The only complaint
that I have about Acton's interlude is that after demolishing the notion
of "fitting exponential data," he fails to point out that this is the
inverse Laplace transform problem. Perhaps if everyone read this and
made the connection, we would be spared the monthly "is there any good
algorithm for the inverse Laplace transform?"
Arge, Bruaset and Langtangen, editors
Modern Software Tools for Scientific Computing
Contains selected contributions from the SciTools'96 conference. Ssee
http://www.oslo.sintef.no/SciTools96/ SciTools96
This book consists of papers discussing topics related to
computational differential equations, computational geometry
and software development. For further information, see
http://www.birkhauser.com/cgi-win/ISBN/0-8176-3974-8 birkhauser
Baker, Louis. 1991
C Mathematical Function Handbook
Daehlen and Tveito, editors
Numerical Methods and Software Tools in Industrial Mathematics
Birkhauser
It includes an introduction to object-oriented numerics and a presentation
of the software tools Diffpack and Siscat. See
http://www.oslo.sintef.no/NAM/ software tools
Also a series of challenging applications are discussed.
For more information, see
http://www.birkhauser.com/cgi-win/ISBN/0-8176-3973-X birkhauser
Dahlquist, Germund; Bjorck, Ake 1974
Numerical Methods
translated by Ned Anderson, Prentice-Hall, 1974.
A nice mix of theory and practice.
Used as a text at Stanford, among other places.[John Chandler]
Dubois, Paul. 1996
Object Technology for Scientific Computing
Object-Oriented Numerical Software in Eiffel and C
Prentice Hall, 1996, paper, 350 pages
ISBN 0-13-267808-X
Comes with CD-ROM
Price: $40.00
Duff, I.S., and G.A. Watson, editors 1996
The State of the Art in Numerical Analysis
[author]:
The 1996 conference on the State of the Art in Numerical Analysis was organized
to provide the numerical analysis community, and users of numerical methods,
with a forum where an account of the important recent developments in the
subject could be presented in a coherent and concentrated way in a manner
accessible to the non-specialist in the sub-area.
Forsythe, George; Moler, Cleve B. 1967
"Computer Solution of Linear Algebraic Systems"
Prentice-Hall
I consider this possibly the best textbook I have ever seen
in any field. Covers only linear systems, of course.[John Chandler]
Gautschi, Walter 1997
Numerical analysis : an introduction
Boston, Mass. : Birkhauser, 1997
A very readable, carefully written book with emphasis
on nonlinear aspects of numerical analysis.
The book is suitable for a first year graduate course and
contains a rich set of examples and exercises. [Jorg Peters]
Golub, Gene H.; Van Loan, Charles F. 1996
Matrix Computations, Third edition
Johns Hopkins, Baltimore
ISBN 0-8018-3739-1
Telephone: 410-516-6900
[SJS] A classic for handling matrices. Many current programs
are based on this text. Good mix of theory and implementation.
Golub, Gene H. 1984
Studies in Numerical Analysis
Mathematical Association of America
ISBN 0883851261.
[Daniel Pick] This contains several outstanding essays from several
numerical analysts, including Wilkinson's The Perfidious Polynomial,
which explains why rootfinding of polynomials numerically is such a
tricky problem. It gives an great introduction to the thinking of
recent numerical analysts. [Amara Graps] All of the chapters are really
good- my favorites are: "Fast Poisson Solvers" and "Multigrid Methods
for Partial Differential Equations."
Kahaner, David; Moler, Cleve; Nash, Stephen. 1989
Numerical Methods and Software
Prentice Hall, Englewood Cliffs, NJ
ISBN 0-13-627258-4
Telephone: 800-947-7700
An excellent book which touches on a variety of topics and makes
use of the publicly available software like the QUADPACK and SLATEC
libraries to illustrate the points. [Vijay Gupta]
Knuth, Donald E. 1981
The Art of Computer Programming: Seminumerical algorithms, 3rd edition.
Addison-Wesley.
Once was the reference; now a bit dated.
Lau, H. T. 1995
A Numerical Library in C for Scientists and Engineers
CRC Press, Boca Raton, FL
ISBN 0-8493-7376-X
Telephone: 407-994-0555
This book is basically a compilation of program listings,
with a diskette containing source code. The listings
are accompanied by brief overviews of the algorithms
involved, and generally include references. There is
no discussion of theory. While the text by Stoer & Bulirsch is at
the theoretical end of the NA spectrum, this text is at the
application end. Although the program calling parameters
are well described, as far as I could see the programs
contain no internal documentation whatsoever.
Although this book is copyright 1995,
the references contain one source dated 1992 (Press et al's volume),
one source dated 1981 (NUMAL in Fortran), and one source dated
1980 (NUMAL in Algol). The remainder of the references
are dated 1976 and earlier. It's not clear to me that this book
offers anything over Press et al's text. Lau has far less discussion of
theory and methodology, and while Press's internal documentation
of programs is poor, Lau's book has none whatsoever. [SJS]
Mathews, John H. 1992
NUMERICAL METHODS: for Mathematics, Science & Engineering
Prentice Hall, Englewood Cliffs, NJ
ISBN 0-13-624990-6 and
ISBN 0-13-625047-5
Source for the programs is available in several languages:
ftp://ftp.mathworks.com/pub/books/mathews/matlab Matlab (ftp)
ftp://ftp.mathworks.com/pub/books/mathews/c C (ftp)
ftp://ftp.mathworks.com/pub/books/mathews/fortran Fortran (ftp)
ftp://ftp.mathworks.com/pub/books/mathews/pascal Pascal (ftp)
http://www.wri.com/MathSource/Publications/BookSupplements/Mathews-1996/0207-874 Mathematica (http)
Muller, Jean-Michel, 1997
Elementary functions, algorithms and Implementation
Birkhauser Boston. See:
http://www.birkhauser.com/cgi-win/ISBN/0-8176-3990-X Birkhauser
http://www.ens-lyon.fr/~jmmuller/book_functions.html Muller
Nash, John C., 1987, 1996
Nonlinear Parameter Estimation: an integrated system in BASIC
Sample chapters and portions of the code are at:
Peters, Martin, 1997
Solving Problems in Scientific Computing Using Maple and MATLAB
All Maple and MATLAB programs can be obtained from:
ftp://ftp.inf.ethz.ch/pub/software/SolvingProblems/ed3/ Peters text
Petkovsek, Marko; Wilf, Herbert; Zeilberger, Doron. 1995
"A=B"
Publisher: AK PETERS, Ltd., 289 Linden Street, Wellesley, MA 02181
Telephone to (617) 235-2210. $39.
ISBN 1-56881-063-6
[Donald Knuth] Science is what we understand well enough
to explain to a computer. Art is everything else we do.
During the past several years an important part of
mathematics has been transformed from an Art to a
Science: No longer do we need to get a brilliant insight in order to
evaluate sums of binomial coefficients, and many similar formulas that
arise frequently in practice; we can now follow a mechanical procedure
and discover the answers quite systematically.
I'm especially pleased to see the appearance of this book, because its
authors have not only played key roles in the new developments, they
are also master expositors of mathematics. It is always a treat to
read their publications, especially when they are discussing really
important stuff.
Science advances whenever an Art becomes a Science. And the state of
the Art advances too, because people always leap into new territory
once they have understood more about the old. This book will help you
reach new frontiers.
Press, William H.; Teukolsky, Saul A.; Vetterling, William A.;
Flannery, Brian P. 1992
Numerical Recipes in C, Second edition
Cambridge University Press, Cambridge and New York
ISBN 0-521-43108-5 Text
ISBN 0-521-43720-2 Example book
ISBN 0-521-43714-8 PC diskette, 5.25 inch
ISBN 0-521-43724-5 PC diskette, 3.5 inch
ISBN 0-521-43715-6 Mac diskette, 3.5 inch
Telephone: 212-924-3900, 800-872-7423
Seperately purchasable diskette contains C source code.
A compendium of a wide variety of NA areas. Contains some
good introductions to theory and overviews of algorithms.
The bridge from algorithm overview to implementation
is often missing. Some of the programs should be viewed with
skepticism. Some are poorly documented, and some users
have reported numerical problems with the various programs. [SJS]
Additional information may be at:
Some Numerical Recipes Reviews are at:
http://www.lysator.liu.se/c/num-recipes-in-c.html N.R. Review
http://math.jpl.nasa.gov/nr/ N.R. Reviews
http://math.jpl.nasa.gov/nr/nr.html N.R. Review
Sedgewick, Robert. 1988
Algorithms, Second edition
Addison-Wesley, Reading, Mass
ISBN 0-201-06673-4
Telephone: 617-944-3700, 800-822-6339
Stewart, Ian. 1999.
Notes on Matrix Algorithms I: Basic Decomposition
Notes on Matrix Algorithms II: Eigensystems
Siam Press.
Parts may be available online at:
http://www.cs.umd.edu/~stewart/ Ian Stewart
Stoer, Josef; Bulirsch, Roland 1980
Introduction to Numerical Analysis
Springer-Verlag, New York, 1980
ISBN 0-387-90420-4
Telephone: 212-460-1500, 800-777-4643
The classic NA text. A standard for graduate
and upper undergraduate courses in NA.
Difficult going, but covers a wide set of fields in depth.
Strong theoretical orientation. [SJS]
Strang, Gilbert 1988
Linear Algebra and It's Applications, Third Edition
Harcourt Brace, San Diego
ISBN 0-15-551005-3
A well-written introduction to theory.
Strang, Gilbert and Borre, Kai 1997
Linear Algebra, Geodesy, and GPS
Wellesley-Cambridge Press Box 812060 Wellesley MA 02181
fax 617 253-4358 phone 781 431-8488 email gs@math.mit.edu
[author]: The book has three closely connected parts.
The first is Linear Algebra,
which is the fundamental tool in positioning calculations. The second is
Geodesy, which includes the correct weightings for observation errors and
the development of least squares. The third is GPS, which we describe in
detail at several levels : first the basic structure of the GPS system, then
the algorithms that yield accurate positions from inaccurate pseudoranges,
and finally the Kalman filtering (and "Bayes" filtering) that give superior
accuracy in postprocessing a long series of observations.
Trefethen, Nick, and Bau, David 1997
Numerical Linear Algebra
Siam
Tyrtyshnikov, Eugene E, 1997
A Brief Introduction to Numerical Analysis.
Birkhauser, Boston.
[author]: "Without any doubt, there are many quite good and
excellent books on the subject. But I know definitely
that I did not realize this when I was a student.
In this book, my first desire was to present those lectures
that I wished I would have heard when I was a student."
Watkins, David S. 1991
Fundamentals of Matrix Computations
John Wiley, New York, 1991.
ISBN 0-471-61414-9
Telephone: 212-850-6000, 800-225-5945
More readable than Stoer & Bulirsch or Golub & Van Loan, and contains
some implementation techniques not present in Golub & Van Loan.
Has good descriptions of theory and implementations,
and many implementations are covered as straightforward exercises.
Not as wide a variety of fields as either Golub & Van Loan or
Stoer & Bulirsch. [SJS]
===========================================================================
q205. Dense Linear Algebra Systems
The best resources for linear algebra are:
The texts by Golub & Van Loan and by Watkins.
On the net, library package LAPACK, with BLAS, from netlib
(see iii q115.1, "Netlib") is a widely recommended replacement
for EISPACK and LINPACK. It handles dense matrices only.
As far as complete packages, nearly all NA packages, both on
the net and commercial, include linear algebra as part of their
core. See the listings above.
See also:
Jack Dongarra's list of Linear Algebra Software
http://www.netlib.org/utk/people/JackDongarra/la-sw.html Dongarra's list
National HPCC Software Exchange Catalog
http://www.nhse.org/rib/repositories/nhse/catalog/ NHSE Catalog
Simpler or smaller systems for linear algebra include:
C.R. Birchenhall's MatClass: matrix and linear algebra system.
ftp://ftp.mcc.ac.uk/pub/matclass/unix Unix version
ftp://ftp.mcc.ac.uk/pub/matclass/pc PC version
[author]: MatClass - a C++ class for numerical computation
Offers a general purpose dense, real matrix class.
Has a family of decomposition classes based on LU, Cholesky, Householder QR
and SVD.
Has a family of OLS regression classes based on above decompositons.
Has a family of special function classes.
Random number class. Has a simplified I/O structure.
Documents : Very thorough tex manual, with discussion of design philosophy.
Currently the manual
does not cover all the features of the I/O.
One user comments that:
From my experience I can say that is very well done.
It covers all the possible
statistical distributions, as well as, random numbers generation from these
distributions.
http://webnz.com/robert/ newmat0.9
[skelton] it is simple, well documented, not templated but easy to
use.
http://math.nist.gov/tnt/index.html TNT
[author]
The Template Numerical Toolkit is a collection of mathematical libraries for numeric computation in C++. Its fundamental classes
include vectors, matrices, and multidimensional arrays. The basic goal is to allow one to express mathematical computation at a higher
level of abstraction, while still retaining some control over performance and optimization issues. Doing so requires a careful analysis to
balance these tradeoffs.
The toolkit provides an integrated collection of generic matrix/vector classes based on components of the Standard Template Library
(STL) and ANSI C++, together with specialization of generic algorithms for maximal efficiency.
The TNT component for linear algebra is a successor to the Lapack++, Sparselib++, IML++, and MV++ packages. Its goal is to
formally integrate these ideas into a generic algorithmic library, supporting user-defined data types, and increasing its functionality. It
also takes advantage of the latest features in the ANSI C++ specification which were not available when we designed our earlier
packages.
[SJS] TNT appears to have a good base of basic linear algebra, but
is not yet as complete as LAPACK. My cursory check found no eigenvalue
facilities.
===================================
q207. Sparse Linear Algebra Systems
Netlib (see iii q115.1, "Netlib") has a number of libraries
for handling sparse systems. See the netlib directories:
sparse, sparse-blas, sparsepak.
See also:
Jack Dongarra's list of Linear Algebra Software
http://www.netlib.org/utk/people/JackDongarra/la-sw.html Dongarra's list
National HPCC Software Exchange Catalog
http://www.nhse.org/rib/repositories/nhse/catalog/ NHSE Catalog
Victor Eijkhout's Overview of Iterative Linear System Solver Packages
http://www.netlib.org/utk/papers/iterative-survey/ Victor Eijkhout's Survey
[N. Sukumar]:
Recommends the TEMPLATES book ["TEMPLATES for the soln of linear systems:
building blocks for iterative methods"] that is availabe in postscript
format at netlib. Also in the same dir is code (in C and Fortran)
for algorithms discussed in the book. "The book is awesome
(easy to read, good pointers on selection of solvers etc.),
especially for one who is not aware of how and why
sparse solvers work."
netlib, in the directory: templates
[N. Sukumar] also recommends:
The sparse package SPARSKIT which also has the solvers
built-in; there are many other feature in addition [matrix conversion/
formatting, plotting, statistics etc].
ftp://ftp.cs.umn.edu/.archive2/users/saad/SPARSKIT U. Minnesota SPARSKIT
ftp://ftp.cs.umn.edu/.archive2/sparse/SPARSKIT2 U. Minnesota SPARSKIT
ftp://icarus.riacs.edu/pub/SPARSKIT U. Minnesota SPARSKIT
PSPASES: A Scalable Parallel Direct Solver for
Sparse Symmetric Positive Definite Systems
http://www-users.cs.umn.edu/~mjoshi/pspases/ PSPASES
by Mahesh Joshi, George Karypis, Vipin Kumar, Anshul Gupta
[authors]: PSPASES is a stand-alone MPI-based
parallel library for solving linear systems of equations involving sparse
symmetric positive definite matrices. The library efficiently implements
the scalable parallel algorithms developed by authors, for each of the four
phases of direct solution method; viz. ordering, symbolic factorization,
numerical Cholesky factorization, and solution of triangular systems.
Aztec: A Parallel Iterative Package for Linear Systems
http://www.cs.sandia.gov/CRF/aztec1.html AZTEC
[authors]:
Aztec is an iterative library that greatly simplifies the parallelization
process when solving the linear systems of equations Ax = b where A is a user
supplied nxn sparse matrix, b is a user supplied vector of length n and x is a
vector of length n to be computed. Aztec is intended as a software tool for
users who want to avoid cumbersome parallel programming details but who have
large sparse linear systems which require an efficiently utilized parallel
processing system. A collection of data transformation tools are provided that
allow for easy creation of distributed sparse unstructured matrices for
parallel solution. Once the distributed matrix is created, computation can be
performed on any of the parallel machines running Aztec: workstation clusters
(DEC, SGI, SUN, LINUX, etc.), Cray T3E, Intel TeraFlop, Intel Paragon, IBM SP2,
nCUBE 2 as well as other MPI platforms, vector machines or serial machines.
Aztec includes a number of Krylov iterative methods such as conjugate gradient
(CG), generalized minimum residual (GMRES) and stabilized biconjugate gradient
(BiCGSTAB) to solve systems of equations. These Krylov methods are used in
conjunction with various preconditioners such as polynomial or domain
decomposition methods using LU or incomplete LU factorizations within
subdomains. Although the matrix A can be general, the package has been designed
for matrices arising from the approximation of partial differential equations
(PDEs).
S+:
http://www.cs.ucsb.edu/projects/s+/ S+
[author]:
Sparse LU factorization with partial pivoting is important for many scientific applications and delivering high performance for this problem is difficult
on distributed memory machines. This project studies the properties of elimination forests and uses them to guide supernode partitioning/amalgamation
and execution scheduling. This design with 2D mapping effectively identifies dense structures without introducing too many zeros in the BLAS
computation and exploits asynchronous parallelism with low buffer space cost. The implementation of this code, called S+, uses supernodal matrix
multiplication which retains the BLAS-3 level efficiency and avoids unnecessary arithmetic operations. This project also studies two space optimization
techniques which can greatly improve the worst-case performance of static symbolic factorization.The experiments show that S+ can achieve up to
10.85GFLOPS on 128 Cray T3E 450MHz nodes, which is the highest performance reported in the literature.
WSMP: Watson Sparse Matrix Package
ftp://ftp.cs.umn.edu/users/kumar/anshul/wsmp1.ps WSMP Part 1
ftp://ftp.cs.umn.edu/users/kumar/anshul/wsmp2.ps WSMP Part 2
[author]:
A Serial/Parallel Direct General/Symmetric Sparse Solver
WSMP (Watson Sparse Matrix Package) is a robust, high-performance, easy-
to-use serial and parallel software for the direct solution of general
and symmetric sparse linear systems on IBM RS6000 and SP platforms.
UMFPACK
http://www.cise.ufl.edu/research/sparse/umfpack/v4.0 UMFPACK
[author]:
UMFPACK V4.0 is a package written in C for sparse LU factorization. The
current version (V4.0beta) can now handle real or complex matrices,
square or rectangular matrices, and non-singular or singular matrices.
A simple MATLAB interface is provided. For example, x = umfpack (A, '\', b)
is like the MATLAB statement x = A\b.
Mondriaan
http://www.math.uu.nl/people/bisseling/Mondriaan/mondriaan.html Mondriaan
Mondriaan is a sparse matrix partitioning package.
Mondriaan is a two-dimensional, multilevel,
hypergraph-based package for the partitioning of a rectangular
sparse matrix, as a sequential preprocessing step for parallel
sparse matrix-vector multiplication.
It is written in C. It is distributed under the GNU license.
EigTool
http://www.comlab.ox.ac.uk/projects/pseudospectra/eigtool/ EigTool
EigTool combines the Pseudospectra GUI with MATLAB's eigs command to
provide visualisation of the Arnoldi iteration during an eigs
computation. It includes all of the existing features of the
Pseudospectra GUI along with several new ones, notably norms of matrix
powers and exponentials and a collection of over 30 demos.
===========================================================================
q210. Random Number Generators (RNGs)
* iii q210.1, "Web Sites for Random Number Generators"
* iii q210.2, "References for Random Number Generators"
* iii q210.3, "Types of Random Number Generators"
* iii q210.6.1, "Linear Congruential Generators (LCG)"
* iii q210.6.2, "Add-with-carry and Subtract-with-borrow Generators (AWCG, SWBG)"
* iii q210.6.3, "Multiply-with-carry Generators (MWCG)"
* iii q210.6.4, "Inversive Conguential Generators (ICG)"
* iii q210.7, "Tests for Randomness"
* iii q210.8, "Commercial RNGs and Hardware RNGs"
===================================
q210.1. Web Sites for Random Number Generators
ftp://odin.mda.uth.tmc.edu/pub/source RANDLIB (C and Fortran versions)
[author]:
The bottom level routines provide 32 virtual random number generators.
Each generator can provide 1,048,576 blocks of numbers, and each block
is of length 1,073,741,824. Any generator can be set to the beginning
or end of the current block or to its starting value. Packaging is
provided so that if these capabilities are not needed, there is a
single generator with period 2.3 X 10^18.
Using this base, routines are provided that return:
(1) Beta random deviates
(2) Chi-square random deviates
(3) Exponential random deviates
(4) F random deviates
(5) Gamma random deviates
(6) Multivariate normal random deviates (mean and covariance
matrix specified)
(7) Noncentral chi-square random deviates
(8) Noncentral F random deviates
(9) Univariate normal random deviates
(10) Random permutations of an integer array
(11) Real uniform random deviates between specified limits
(12) Binomial random deviates
(13) Negative Binomial random deviates
(14) Multinomial random deviates
(15) Poisson random deviates
(16) Integer uniform deviates between specified limits
(17) Seeds for the random number generator calculated from a
character string
pLab is an excellent web site created by the Department
of Mathematics at the Salzburg University. It covers
RNGs and tests for randomness, and contains publications,
software, and pointers to other resources. Use either:
http://random.mat.sbg.ac.at/ Salzburg Dept. Mathematics
http://www.sbg.ac.at/home.htm Salzburg Dept. Mathematics
Additional services may be available from pLab -- see:
http://crypto.mat.sbg.ac.at/ pLab Overview
Another web page with info on RNGs is Skip Carter's page at Taygeta:
http://www.taygeta.com/random.html Skip Carter's page
See also the Diehard page, described at:
iii q210.7, "Tests for Randomness"
Also see Pierre L'Ecuyer's papers:
http://www.iro.umontreal.ca/~lecuyer/ L'Ecuyer
Info on 1/f noise, called "flicker noise" or "pink noise", is at:
http://linkage.rockefeller.edu/wli/1fnoise/ Wentian Li's site
Alan Miller's Page:
http://members.ozemail.com.au/~milleraj/ Alan Miller
Some code in Fortran 90 for generating random numbers from a range
of discrete and continuous distributions
SPRNG: Scalable Parallel Random Number Generator Library
http://sprng.cs.fsu.edu/ SPRNG
We are happy to announce the Beta release of SPRNG: a Scalable
Parallel Random Number Generator Library. (It can be used for the usual
serial random number generation too.)
===================================
q210.2. References for Random Number Generators
References:
V.S.Anashin. Uniformly distributed sequences over $p$-adic integers. - In:"
Number Theoretic and Algebraic Methods in Computer Science. Proc. Int'l Conf.
Moscow, June - July 1993". Alf J van der Poorten, Igor Shparlinsky and Horst G.
Zimmer - editors. Published by World Scientific, 1995. Pp. 1 -18.
Anashin, V. S., Uniformly distributed sequences of $p$-adic integers
(Russian), Mat. Zametki 55 (1994), no. 2, 3--46, 188; MR 95f:11096 There is
an English translation of this paper made by Plenum Publ. Corp.
Anashin, V.S. Uniformly distributed sequences in computer algebra or how to
construct random number generators. Translated from
Itogi Nauki i Tekhniki, Seria Sovremennaya Matematika i Ee
Prilozheniya. Tematicheskie Obzory, Vol.
31, Computing Mathematics and Cybernetics - 2, 1995. 1072 - 3374/96/0000 -
0001. Plenum Publisning Corp., 1996
Anashin, V. S., Solvable groups with operators and commutative rings having
transitive polynomials (Russian), Algebra i Logika 21 (1982), no. 6,
627--646; MR 85d:20028
Law, Averill M, and Kelton, W. David. 1991
Simulation Modeling & Analysis, Second edition
McGraw Hill, New York
Banks, Jerry. Handbook on Simulation
Wiley.
Bratley, P., Fox, B.L. & Schrage, L.E. 1987
A guide to simulation, 2nd edition
Springer
Devroye, Luc. 1986
Non-uniform random variate generation
Springer-Verlag, New York
[SJS] This is the most complete book I've found on generating non-uniform
random values.
L'Ecuyer, Pierre. Random numbers for simulation. Comm. ACM 33, 85-97 (1990) .
L'Ecuyer, Pierre. Uniform random number generation.
Annals of operations research 53 (1994), 77.
Leva, Joseph L. (1992). A Fast Normal Random Number Generator,
ACM Transactions on Mathematical Software, 18(4), pp. 449-453.
Marsaglia, George. JACM 12 (1965), 83-89.
Marsaglia, George. "Random numbers fall mainly in the planes",
Proc. Nat. Acad. Sciences USA, 61 (1968), 25-28.
Marsaglia, George. "Remarks on choosing and implementing
random number generators", Communications of the ACM v 36
n 7 (July 1993), p 105-107.
Marsaglia, George and Zaman, Arif. "A new class of
random number generators". The annals of applied
probability 1, 3, (1991), p. 462-480.
Motwani, Rajeev and Raghavan, Prabhakar 1995
Randomized Algorithms
Cambridge University Press
Sullivan, Stephen. "Another test for randomness",
Communications of the ACM 36, 7 (July 1993), p 107.
Tezuka, Hsh, L'Ecuyer, Pierre, and Couture, Raymond.
"On the lattice structure of add-with-carry and subtract-with-
borrow random number generators", ACM Trans on Modeling and
Computer Simulation 3, 4 (October 1993), p. 315-331.
Still more references, courtesy of [Ripley]:
James, F. (1990) A review of pseudorandom numbers. Comp.
Phys. Comm. 60 329--344.
Morgan, B.J.T. (1984) Elements of simulation. Chapman & Hall.
Ripley, B.D. (1983) The computer generation of random variables
- a tutorial. Int. Statist. Rev. 51 301--319.
Ripley, B.D. (1987) Stochastic Simulation. Wiley, New York
Ripley, B.D. (1990) Thoughts on pseudorandom number generators.
J. Comput. Appl. Math. 31, 153--163.
A revised version of the last is available by anonymous ftp from
ftp://markov.stats.ox.ac.uk/pub/simul/prng.ps.Z Ripley's Paper
Eichenauer-Herrmann, J. (1992) Inversive congruential pseudorandom
numbers: a tutorial. Int. Statist. Rev. 60, 167-176
===================================
q210.3. Types of Random Number Generators
Random number generators typically consist of three components:
* The basic generator, described further below.
* Some generators contain a shuffle box. First described
in Marsaglia 1965. Also described in Knuth 1981 and Press et al 1992.
* A transformation to the desired probability distribution.
See Press et al 1992 or, better yet, Law 1991 or Devroye 1986.
There are four common types of basic generators.
* iii q210.6.1, "linear congruential (LCG)"
* iii q210.6.2, "add-with-carry and subtract-with-borrow (AWCG, SWBG)"
* iii q210.6.3, "multiply-with-carry (MWCG)"
* iii q210.6.4, "inversive conguential (ICG)"
===================================
q210.6.1. Linear Congruential Generators (LCG)
Linear congruential generators are of the form
x(n) = a * x(n-1) + b mod M
A good discussion of this type is in the text by Press et al.
These are by far the most common form in use, and have periods
in the range 10^6 to 10^9 when using 32 bit words. Unfortunately,
they have some unpleasant properties. When taken in pairs,
triplets, or n-tuples, the random values often fall on only
a few planes in n-space. Using a shuffle box can
break up this uniformity. For more information on the
problems associated with linear congruential generators,
see Marsaglia 1968, Marsaglia 1993 and Sullivan 1993.
See also Marsaglia's web site, described under
iii q210.7, "Tests for Randomness".
===================================
q210.6.2. Add-with-carry and Subtract-with-borrow Generators (AWCG, SWBG)
Add-with-carry generators have the form:
x(n) = x(n-s) + x(n-r) + carry mod M
Subtract-with-borrow generators have the form:
x(n) = x(n-s) - x(n-r) - carry mod M
See Marsaglia 1991.
These generators have much longer periods, from 10^200 to 10^500,
than LCGs, and they are almost as fast as LCGs.
Unfortunately they too have the problem of falling
mainly on the planes. See Tezuka 1993.
Again, a shuffle box, as described in Press et al, can eliminate
this problem.
The implementation by Marsaglia and Zaman may be found at:
ftp://ftp.wustl.edu/systems/ibmpc/msdos/math/fsultra1.zip Marsaglia
===================================
q210.6.3. Multiply-with-carry Generators (MWCG)
Multiply-with-carry generators have the form:
x(n) = a*x(n-1) + carry mod M
[George Marsaglia]:
Here is a simple version, one so simple and good I predict
it will be the system generator for many future computers:
x(n)=a*x(n-1)+carry mod 2^32
With multiplier 'a' chosen from a large set of easily found
integers, the period is a*2^31-1, around 2^60, and
I have yet to find a test it will not pass!
[Charles Knechtel]:
George Marsaglia has some interesting new ideas for pseudorandom number
generation using MWCG and MWCG combined with other pseudorandom number
generators (RNGs); these new ideas are implemented as part of the Diehard
suite of RNG tests. The best of these seem to pass
all the Diehard tests, even tests that many common pseudorandom number
generators fail.
Source is at the Diehard page, described at:
iii q210.7, "Tests for Randomness".
===================================
q210.6.4. Inversive Conguential Generators (ICG)
Inversive congruential generators are of the form
x(n) = a * ~(x(n-1)) + b mod M
where:
M is prime
"~y" denotes the multiplicative inverse of y in
the field over {0, 1, ..., M-1} using arithmetic modulo M,
and ~0 is 0.
ICGs do not have the "mainly in the planes" problem.
See the pLab, described above at
iii q210.1, "Web Sites for Random Number Generators",
for more info on ICGs.
[Charles Knechtel]:
Marsaglia's Diehard suite of RNG tests, at
iii q210.7, "Tests for Randomness"
also contains a subroutine named
makeinvc which implements an ICG and generates a file of pseudorandom
numbers named INVCONG.32; however, examination of the FORTRAN source code
for makeinvc shows that a modulus M equal to 2^32 was used (see file
makewhat.f. Eichenauer-Herrmann (1992, p. 173, 175) notes that
certain ICGs with power of two modulus have distributional disadvantages
compared to the "excellent quality" of ICGs with prime modulus. Indeed,
the documentation for INVCONG.32 remarks that makeinvc fails to pass many
of the Diehard tests (see the last section of file makef.txt from
the Diehard archive fortran.tar.gz. An ICG with prime
modulus should have better uniform properties than makeinvc, and Otmar
Lendl's ICG implementation might be speedier than makeinvc.
===================================
q210.7. Tests for Randomness
The Diehard suite of RNG generators and tests,
by George Marsaglia, is available from:
http://stat.fsu.edu/~geo/diehard.html Diehard overview, source, & binaries
For snapshots of some of the graphs, see:
http://euler.bd.psu.edu/~naras/diehard/snapshots.html Diehard snapshots
A GUI version of Diehard is in preparation by Dr. Balasubramanian
Narasimhan at:
http://www-stat.stanford.edu/~naras/diehard/snapshots.html Diehard GUI
Also see pLab, described above at
iii q210.1, "Web Sites for Random Number Generators",
for descriptions of some tests.
===================================
q210.8. Commercial RNGs and Hardware RNGs
http://webnz.com/robert/true_rng.html Robert Davies' page
Robert Davies has a comparison of hardware and software RNGs.
http://www.protego.se Protego Hardware Generator
[author]:
No more unreliable generation of crypto keys
and random numbers in software, the viable
alternative is here! SG100 Security Generator
is an easy to use easy to integrate hardware
random number generator that connects to the
standard serial port. Complete with driver
software for Windows 95/Windows NT and
example programs in source.
SG100 is the choice if you want to strengthen
and enhance your encryption, statistics and
simulation software.
===========================================================================
q215. Function Evaluation
Point to some sources in netlib, statlib and elsewhere?
If you'd like to write a paragraph for the FAQ on function evaluation,
please contact me ...
===========================================================================
q220. Finding Roots
This is a standard topic in nearly all general texts on NA, and
many routines exist in netlib (see iii q115.1, "Netlib")
and other libraries.
See also Alan Miller's Page:
http://members.ozemail.com.au/~milleraj/ Alan Miller
An algorithm for finding the roots of polynomial equations.
It is a translation into Fortran 90 of the version of Aberth's
method by D. Bini in Numerical Algorithms, v.13 (1996), 179-200.
The Fortran 77 code for this algorithm can be obtained from the
numeralgo directory of netlib.
===========================================================================
q230. Curve Fitting, Data Modelling, Interpolation, Extrapolation
This vague heading covers a multitude of closely related endeavors.
There are many approaches, described in the following sections.
* iii q230.1, "Interpolation"
* iii q230.2, "Statistical Curve Fitting"
* iii q230.2.1, "Levenberg-Marquardt algorithm"
* iii q230.4, "Time series analysis"
* iii q230.6, "Splines"
* iii q230.7, "Nearest Neighbor algorithms"
* iii q230.8, "Fitting a circle to a set of points"
* iii q230.9, "ZunZun Interactive curve fitting"
Commercial packages:
* iii q230.10, "CurveExpert"
Other approaches to data modelling are:
* iii q550, "Neural Networks".
* iii q245, "Wavelets".
===================================
q230.1. Interpolation
For one dimensional work, see Stoer & Bulirsch 1980 or Press et al 1992.
No doubt some of the techniques described there can
be found in netlib (see iii q115.1, "Netlib") by using the NIST guide
(see iii q110, "Indices of NA Software on the Net").
For greater than or equal one dimensions, some references are:
Dave Watson's home page:
http://members.iinet.net.au/~watson/software.html Dave Watson's Software
Watson, Dave 1992
Contouring: A guide to the analysis and display of spatial data,
Pergamon Press
ISBN 0 08 040286 0
Text includes a floppy with source code in Basic (sigh). Subject areas:
isoline maps, isochor maps, methodology, data sorting, subset selection,
local coordinates, binary local coordinates, barycentric coordinates,
rectangular local coordinates, natural neighbour coordinates,
gradient estimation, least squares gradients, least squares quadratics,
spline gradients, cross product gradients, neighbourhood-based gradients,
interpolation, inverse distance weighting, inverse distance weighted
gradients, minimum curvature splines, neighbourhood-based interpolation,
selected references to contouring literature
[Dave Watson] writes:
Linear triangle-based interpolation
is quick and dirty - probably the best compromise available if you are
in a hurry. Natural neighbor interpolation is much slower but does
provide a result that most people consider to be closest to that which an
experienced manual draftsman would generate.
The 'kriging' method is a
variation on the splines technique - the main difference being that a
subjectively selected probabilistic function is used rather than one of
the analytically derived radial basis functions. This class of method
generates discontinuities at points where the interpolation subset
changes, and kriging attempts to ameliorate this effect be recomputing
the coefficients for each interpolation point - this makes it very slow.
Interpolation on spheres:
See the FAQ by Dave Rusin:
http://www.math.niu.edu/~rusin/known-math/index/spheres.html Rusin's FAQ
See also the comp.graphics.algorithms FAQ:
http://www.faqs.org/faqs/graphics/algorithms-faq/ graphics FAQ
http://exaflop.org/docs/cgafaq/ graphics FAQ
Software:
[Albrecht Preusser] wrote:
You could take routines from ACM Alg. 624 "Triangulation and Interpolation
of Arbitrarily Distributed Points in the Plane" by Robert J. Renka.
This Algorithm is available from netlib (see iii q115.1, "Netlib")
in the toms directory.
Another algorithm in FORTRAN is contained in Akima's ACM Alg. 526,
it is faster, but takes much more memory. By the way, I have developed
methods based on the Delaunay Triangulation from both algorithms for
computing nonlinear contours and nonlinear interpolation, which are
published as ACM Alg. 626 and 684.
Spatial and Geometric Analysis toolbox (SaGA) -
a MATLAB package for various aspects of spatial data
interpolation and analysis and geometric modeling.
It is available at:
http://puddle.mit.edu/~glenn/kirill/saga.html Glenn Kirill
OAX:
http://www.tuns.ca/~hey/ocean/oview.html OAX
[author]:
OAX is an spacial objective analysis program. OAX applies the method
of optimal interpolation (objective analysis) to estimate the values of
variables at specified points in a multidimensional space. For each point,
the computation is based on a weighted average of the values of a
specified number of data points (i.e. "nearest neighbours") which are
closest to that point. For the sake of efficiency, several dependent
variables can be interpolated simultaneously using the same weights if
the underlying statistical model and relative noise level in the input data
are assumed to be same for each dependent variable.
In this version, OAX extends the capability of earlier implementations
(OPTIMAL_ESTIMATOR directive, oax3.0, oax4.0) by allowing the
parameters controlling the calculation of the weights to vary as a
function of the independent variables, and by allowing the specification
of a relative uncertainty (NOISE) for each input data record separately.
===================================
q230.2. Statistical Curve Fitting
See also: iii q505, "Probability and Statistics".
See also: iii q230.2.1, "Levenberg-Marquardt algorithm"
Books
Jobson, J.D.
Applied Multivariate Data Analysis, volumes 1 and 2.
Springer-Verlag, New York. 1991.
Johnson, Richard A.; Wichern, Dean W.
Applied Multivariate Statistical Analysis, Third Edition
[Ramin Samadani] writes:
I like the book by Lawson and Hanson, solving
least squares problems. I think its supposed to be back in print now or soon.
Lawson, Charles L.; Hanson, Richard J.
Prentice-Hall, Englewood Cliffs, N.J. 1974
Press et al 1991 also has a description of the field.
Spaeth, Helmuth: "Mathematical Algorithms for Linear Regression"
1987, Academic Press.
Software
ODRPACK, from netlib
[author]:
ODRPACK is a portable collection of Fortran subprograms
for fitting a model to data. It is designed primarily for
instances when the explanatory as well as the response variables
have significant errors, implementing a highly efficient
algorithm for solving the weighted orthogonal distance regression
problem, i.e., for minimizing the sum of the squares of the weighted
orthogonal distances between each data point and the curve described
by the model equation.
===================================
q230.2.1. Levenberg-Marquardt algorithm
[Alan Miller]:
The non-linear least-squares problem is to find a vector of parameter
values, a, to minimize the sum of squares of differences between a
given vector, y, of observed values and a vector of fitted values
f(a,x) where the values of x are known. e.g. a particularly notorious
problem is to fit:
y = a(0) + a(1).exp(-a(2).x) + a(3).exp(-a(4).x)
sometimes with more exponential terms, to a set of (x,y)-pairs.
Writing S = sum [y(i) - f(a,x(i))]^2, where i denotes the i-th observation
pair, we have that the first and second derivatives of S with respect to
the parameters, a(j), are:
S' = -2.sum [r(i).(df/da(j))]
S'' = 2.sum [(df/da(j)).(df/da(k))] - 2.sum [r(i).d2f/(da(j)da(k))]
where r(i) is the i-th residual = y(i) - f(a,x(i)).
The Gauss-Newton (G-N) method uses the linearization of f about the latest
estimates of a, and solves a linear least sqaures problem to obtain a
new vector a.
If J denotes the Jacobian = the n x k matrix of values of (df/da(j)) at
the current estimates of the parameter values, where n is the number of
observations and k is the number of parameters, then the G-N method ignores
the second derivatives of f in S'' and uses
a(new) = a(old) + inv(J'J).J'r
This guarantees a downhill search direction but often overshoots unless
good starting values are available.
The Levenberg-Marquardt (L-M) method uses a trust-region approach, also
known as ridge regression or regularization, to shrink the step sizes to
ensure a reduction in S at each iteration. In the L-M method
a(new) = a(old) + inv(J'J + D).J'r
where D is a diagonal matrix. Levenberg suggested that D = d.I, that is
that the same scalar value be added to each diagonal element. In practice,
the diagonal elements of J'J are often of vastly different magnitudes,
and Marquardt suggested D = lambda.diag(J'J). For the first iteration,
lambda is given a fairly large value (say 1.0). If the first attempt
at an iteration reduces S then lambda is reduced for the next iteration
by a factor of say 5-10. If the first step increases S then lambda is
increased by a factor of perhaps 3-5 until S is reduced. The final
value of lambda for the iteration is then used for the next iteration.
The L-M method converges upon a stationary point (or sometimes a sub-space)
which may be the minimum which is being sought, but it could be a
saddle-point, a local minimum, or one or more of the parameter values may
tend to infinity.
The Jacobian of first derivatives is often ill-conditioned so that QR
factorizations are usually employed to solve the LS equations.
The L-M algorithm is often very efficient. Methods which use second
derivatives require substantially more computation and then it is
common to find that the Hessian matrix is not positive definite very
close to the minimum.
Software:
MINPACK includes L-M algorithms using either analytic derivatives or
derivatives estimated from differences. Obtain from the minpack
directory of netlib.
For many problems, the function f is linear in some of the parameters.
In the sum of exponentials example mentioned, f is linear in a(0), a(1)
and a(3). The VARPRO code uses an L-M type of algorithm but separates
the linear from the non-linear parameters. This code is available from
the opt directory of netlib.
The package NL2SOL (TOMS algorithm 573) uses a hybrid combination of G-N
and estimation of a positive-definite approximation to the Hessian from
differences of first derivatives. It is available from the toms
directory of netlib (Fortran 90 version from
http://members.ozemail.com.au/~milleraj/ Alan Miller
Updates which allow for bounds on parameter values can be found in netlib
directory port with file names starting n2f, n2g, rn2f or rn2g.
There is a very easy-to-use shareware package for PCs including graphics
(NLREG) which is based upon the NL2SOL package, and includes graphics.
It is more successful than many of the non-linear least-squares solvers found
in commercial statistical packages. It can be downloaded from the math
directory of simtelnet.
References:
Bevington, Philip, R.; D. Keith Robinson (1992)
Data Reduction and Error Analysis for the Physical
Sciences (Book and Disk)
Published by McGraw Hill Text
ISBN: 0079112439
Dennis, J.E., Gay, D.M. and Welsch, R.E. (1981). TOMS algorithm 573
(NL2SOL): An adaptive nonlinear least-squares algorithm, ACM Trans. on
Math. Software, v.7, 348-368 and 369-383.
Golub, G.H. and Pereyra, V. (1973). The differentiation of pseudoinverses
and nonlinear least squares problems whose variables separate, SIAM J.
Numer. Anal., v.10, 413-432.
Levenberg, K. (1944). A method for the solution of certain nonlinear
problems in least squares. Qty. Appl. Math., v.2, 164-168.
Marquardt, D.W. (1963). An algorithm for the estimation of non-linear
parameters, SIAM J., v.11, 431-441.
Seber, G.A.F. and Wild, C.J. (1989). Nonlinear regression. Wiley.
===================================
q230.4. Time series analysis
Time series analysis may be used for some types of data.
See:
Brockwell, Peter J.; Davis, Richard A. 1991
Time Series: Theory and Methods, Second Edition
Springer-Verlag, New York.
ISBN 0-387-97429-6
[SJS]: Beautiful approach with emphasis on theory.
Emphasis on the linear model.
Hamilton, James D. 1994
Time Series Analysis
Princeton U. Press, Princeton, NJ
ISBN 0-691-04289-6
[SJS]: Applied approach, with heavy emphasis on applications from
economics. Not having an economics background is a detriment in
reading this text. Broad mix of models.
Montgomery, Douglas C. / Forecasting and time series analysis (1990)
Pankratz, Alan / Forecasting with Univariate Time Series Models:
Concepts and Cases / (1983) / good, clear
Vandaele, Walter / Applied Time Series and Box-Jenkins Models (1983) /
/ good; pedagogical and practical
ARfit: A Matlab package for the estimation and spectral
decomposition of multivariate autoregressive models
http://www.gps.caltech.edu/~tapio/arfit/ ARfit
[author]:
ARfit is a collection of Matlab routines for
* estimation of parameters and confidence regions for multivariate
autoregressive (AR) processes,
* diagnostic checking of fitted models, and
* spectral decomposition of AR models,
ARfit may be freely distributed. Suggestions for improvement are
greatly appreciated.
M-files, documentation, and a paper describing the algorithms used
are available.
Also see iii q115.3, "Statlib".
Also see iii q505, "Probability and Statistics".
===================================
q230.6. Splines
Useful for modelling single and multiple dimensional data.
Books:
de Boor, Carl 1978
A Practical Guide to Splines
Springer-Verlag, New York.
ISBN 0-540-90356-9
[Tim Strotman]: Provides an excellent blending of theory
and practical implementation.
Dierckx, Paul 1993
Curve and surface fitting with splines
Clarendon Press, Oxford England and New York
ISBN 0198534418
Farin, Gerald E. 1995
NURB curves and surfaces : from projective geometry to practical use
Wellesley, Mass. : A.K. Peters
ISBN 1568810385 :
Farin, Gerald E. 1993
Curves and surfaces for computer aided geometric design : a practical
guide, third edition.
Boston : Academic Press
Nurnberger, Gunther 1989
Approximation by Spline Functions
Springer-Verlag, Berlin
ISBN 3-540-51618-2 Berlin
ISBN 0-387-51618-2 New York
Piegl, Les; Tiller, Wayne 1995
The NURBS Book
Springer-Verlag, New York.
ISBN 0-387-55069-0
[Tim Strotman]: Provides an excellent blending of theory
and practical implementation.
Spaeth, Helmuth 1995
One Dimensional Spline Interpolation Algorithms
A.K. Peters, Wellesley, MA
ISBN 1-56881-016-4
Spaeth, Helmuth, and A.K. Peters 1995
Twodimensional Spline Interpolation Algorithms
A.K. Peters, Wellesley, MA
ISBN 1-56881-017-2
Wahba, Grace 1990
t Spline Models for Observational Data
Software:
A search of the NIST guide (see iii q110, "Indices of NA Software on the Net")
turns up numerous references.
===================================
q230.7. Nearest Neighbor algorithms
Books:
Dasarathy, Belur V. 1991
Nearest Neighbor (NN) Norms: NN Pattern Classification Techniques
IEEE Computer Society Press, Los Alamitos, CA
[SJS]: Excellent.
Other references:
The following Technical Reports are available from the International
Computer Science Institute via anonymous FTP from
ftp.ICSI.Berkeley.EDU Berkeley Tech Reports
tr-89-063.ps.Z Five Balltree Construction Algorithms
tr-90-001.ps.Z The Delaunay Triangulation and Function Learning
Teillaud, Monique
Towards Dynamic Randomized Algorithms in Computational Geometry
Lecture Notes in Computer Science 758
Springer-Verlag
Mulmuley, K.; Sen, S.
Dynamic point location in arrangements of hyperplanes
7th ACM Symposium of Computational Geometry in North Conway 1991
M. Dickerson, R. L. Drysdale and J.-R. Sack
Simple algorithms for enumerating interpoint distances
and finding k nearest neighbors.
Internat. J. Computational Geometry & Applications 2:3 (1992) 221--239.
P. B. Callahan and S. R. Kosaraju
A decomposition of multi-dimensional point-sets with
applications to k-nearest-neighbors and n-body potential fields.
24th ACM Symp. Theory of Computing, 1992, 546--556.
M. T. Dickerson and D. Eppstein
Algorithms for proximity problems in higher dimensions.
Comp. Geom. Theory & Applications, to appear.
P. M. Vaidya
An $O(n \log n)$ algorithm for the all-nearest-neighbors
problem.
Discrete and Computational Geometry 4 (1989) 101--115.
===================================
q230.8. Fitting a circle to a set of points
Problem: Given N Points: (x1,y1); (x2,y2).. (xN,yN), we want to find for
best-fit circle: (X0,Y0), R. (Note: for fitting an *ellipse*, substitute
the equation for an ellipse for the equation for a circle in the "Brute
Force Approach").
Brute Force Approach (leads to a non-linear system): [Amara Graps]
Idea: Minimize by least squares the root-mean-squared error of the
radius in the equation for a circle. In this method, one minimizes the
sum of the squares of the *length* differences, which gives you a
non-linear problem with all the associated pitfalls.
(x-X0)^2 + (y-Y0)^2 = R^2 Equation for a circle
R = SQRT[ (x-X0)^2 + (y-Y0)^2) ] Radius of the circle
where:
(X0,Y0) = center of circle
(x,y) = point coordinates
R = radius
1) Get first estimate for (X0,Y0,R).
(Details: Find some points to make first estimates- either solve the
circle exactly (3 equations, 3 unknowns) to get a first estimate of the
center and radius, or just do a kind of centroid calculation on all
points- to get a rough estimate of the center and radius.)
2) Calculate r (r1, r2,.. rN) for each of your N points from the
equation for a radius of a circle.
3) Calculate the root-mean-squared error
For example, for 5 given points on the circle:
RMS error = SQRT[ [ (r1-R)^2 + (r2-R)^2 + (r3-R)^2 + (r4-R)^2
+ (r5-R)^2] / 3 ]
(dividing by "3" because we have 3 free parameters.)
4) Change (X0,Y0,R) slightly in your minimization algorithm
to try a new (X0,Y0,R).
MINIMIZATION DETAILS.
---------------------------------------------------------
Because minimization algorithms can get very computationally
intensive, if one's circle-fitting problem is simple, I would look for
a "canned" minimization routine. Some commercial computer programs for
plotting and spreadsheets do this sort of thing. For example, the
Excel spreadsheet has the built-in "Solver" that will perform
minimzation.
Other possibilties for software.
Matlab with the optimization toolbox.
http://cow.physics.wisc.edu/~craigm/idl/idl.html IDL with Markwardt's MPFIT
or MACSYMA. [Amara Graps]
ODRPACK from Netlib is an excellent library for a production mode
approach to fitting these data, with a graphical user interface at
http://plato.la.asu.edu/guide.html Plato Guide
At the very beginning of the
User's Guide there is a description of how to fit data to an ellipse
or circle. [Don Wells, Hans D. Mittelmann]
http://plato.la.asu.edu/topics/problems/nlolsq.html Plato: Least Squares
Gaussfit is a superb response to the whole family of problems of
adjusting parameters to fit functions to data; it is especially
effective and easy to use for one-time problems and for exploratory
work [Don Wells].
The L-BFGS-B Nonlinear Optimization package allows one to specify
bounds on the variables, from:
http://www.ece.nwu.edu/~nocedal/lbfgsb.html L-BFGS-B
[Helmut Jarausch].
The Fortran programs fcircle.f, fellipse.f and the Lawson & Hanson
least-squares routines ls.f shows how to implement these
least-squares problems at:
ftp://obsftp.unige.ch/fit fcircle.f, fellipse.f, etc.
Alan Miller has updated the above for Fortran 90.
The least-squares software is at:
http://members.ozemail.com.au/~milleraj/ Alan Miller's Sofware
with a working example at:
http://members.ozemail.com.au/~milleraj/lsq/fellipse.f90 Alan Miller's Example
Some Web Guides [Amara Graps]
http://www.graphpad.com/www/nonling1.htm GraphPad Guid to Nonlinear Regression
User's Manual -- GaussFit: {A} system for least squares and robust
estimation", William H. Jefferys and Michael J. Fitzpatrick and
Barbara E. McArthur and James E. McCartney",
ftp://clyde.as.utexas.edu/pub/gaussfit/ [Don Wells]
Other Papers
I. Kasa, "A Curve Fitting Procedure and Its Error Analysis", IEEE
Trans. on Inst. Meas., 3/96, describes an algorithm that is a
modified least squares analysis that uses the difference of the
square of the radii rather than the absolute difference.
[Rod Loewen]
M. Pilu, A. Fitzgibbon, R.Fisher, "Ellipse-specific Direct
least-square Fitting", IEEE International Conference on Image
Processing, Lausanne, September 1996.
http://vision.dai.ed.ac.uk/maurizp/ElliFitDemo/Paper/icip.html Pile et al
A Java demo is at:
http://hplbwww.hpl.hp.com/people/mp/research/ellipse.htm Java Demo
[Amara Graps]
Moura, L. and Kitney, R. I. (1991). A direct method for least
-squares circle fitting. Computer Physics Communications 64, 57-63.
[Colin B. Desmond]
"A Buyers Guide to Conic Fitting", A.W. Fitzgibbon, British Machine
Vision Conference, 1995.
Cunningharn, Robert W.: Comparison of three methods for determining
fit parameter uncertainties for the Marquardt Compromise, Computers
in Physics 7(5), 570, (1993) [Amara Graps]
W. Gander, G. H. Golub and R. Strebel Least Squares Fitting of
Circles and Ellipses BIT vol.34, 1994, pgs. 558-578 [Suhail A
Islam].
Berman & Somlo: "Efficient procedures for fitting circles..." IEEE
Instrum & Meast., IM-35, no.1, pp. 31-35, 1986. [Peter Somlo]
Paul T. Boggs and Richard H. Byrd and Robert B. Schnabel, "A Stable
and efficient algorithm for nonlinear orthogonal distance
regression, SIAM Journal on Scientific and Statistical Computing,
1987, 8, 6,1052-1078 [Don Wells].
P. T. Boggs and J. R. Donaldson and R. H. Byrd and R. B. Snabel,
"Algorithm 676, {ODRPACK} -- Software for Weighted orthogonal
distance regression", ACM Transactions On Mathematical Software,
1989, 15, 348-364 [Don Wells].
---------------------------------------------------------
5) Calculate r (r1, r2 etc.) again from new (X0,Y0,R) above.
6) Calculate RMS error again.
7) Compare current RMS error with previous RMS error. If it
doesn't vary by more some small amount, say 10^{-3} then
you're done, otherwise continue steps 4 -- 7.
Other (more elegant) approaches that reduce to a linear system.
If you choose to minimize the squares of the *area* differences, you get
a linear problem, which is a much safer way. [Pawel Gora, Zdislav V.
Kovarik, Daniel Pfenniger, Condensed by Amara Graps]
1. Function to minimize is (sum of the area differences):
Q = Sum { [ (xi - X0)^2 + (yi -Y0)^2 - R^2 ]^2 , i=1..N }
2. A necessary condition is the system of 3 equations with 3 unknowns
X0, Y0, R. Calculate the partial derivatives of Q, with respect to
X0, Y0, R. (all d's are partial)
dQ / dX0 = 0
dQ / dY0 = 0
dQ / dR = 0
3. Developing we get the linear least-squares problem:
| x1 y1 1 | | a | | -x1^2-y1^2 |
| x2 y2 1 | | b | =~ | -x2^2-y2^2 |
| x3 y3 1 | | c | | -x3^2-y3^2 |
| x4 y4 1 | | -x4^2-y4^2 |
| x5 y5 1 | | -x5^2-y5^2 |
..... .........
(for example, for 5 points)
where a = -2 X0; b = -2 Y0 ; c = X0^2 + Y0^2 - R^2.
Take any good least-squares algorithm to solve it, yielding a,b,c.
So the final circle solution will be given with
X0 = -a/2; Y0 = -b/2; R^2 = X0^2+Y0^2 - c.
By the way, with 5 points you can also find the unique quadratic form
(ellipse, hyperbola) which passes exactly through 5 points.
With more than 5 points one can do a linear least-squares as well.
The problem is then to minimize:
| x1^2-y1^2 x1y1 x1 y1 1 | | a | | -x1^2-y1^2 |
| x2^2-y2^2 x2y2 x2 y2 1 | | b | =~ | -x2^2-y2^2 |
| x3^2-y3^2 x3y3 x3 y3 1 | | c | | -x3^2-y3^2 |
| x4^2-y4^2 x4y4 x4 y4 1 | | e | | -x4^2-y4^2 |
| x5^2-y5^2 x5y5 x5 y5 1 | | f | | -x5^2-y5^2 |
..... .........
The robust or L1 or least-first-power approximation [Zdislav V.
Kovarik].
If you try to minimize
W(a,b,r) = SUM(j=1:N) ABS (((x_j-a)^2 + (y_j-b)^2)^(1/2) - r)
all you have to do is set up the 10 (i.e. if 5, choose 3) circles
passing through every choice of 3 of 5 points, calculate W(a,b,r) for
each of them and pick the minimizing circle. The extra feature is that
this procedure separates and discards points which are conspicuously
far from the majority trend. (Of course, it becomes increasingly
time-consuming when the number of given points increases.)
This method of determining the minimum bounding circle from
a set of _circles_ is solved, and with code available at:
http://www.intergalact.com/circles.html [Sky Coyote]
===================================
q230.9. ZunZun Interactive 2D and 3D Data Modeling
http://www.zunzun.com/ ZunZun
Online interactive fitting and graphing for 2D and 3D data sets.
===================================
q230.10. CurveExpert
http://www.ebicom.net/~dhyams/cvxpt.htm CurveExpert
[author]:
CurveExpert 1.3 is a comprehensive curve fitting system for Windows. XY data can be
modelled using a toolbox of linear regression models, nonlinear regression models,
interpolation, or splines. Over 30 models are built-in, but custom regression models may
also be defined by the user. Full-featured graphing capability allows thorough
examination of the curve fit. The process of finding the best fit can be automated by
letting CurveExpert compare your data to each model to choose the best curve. This
program was designed to be simple but powerful, so that all users can obtain a model for
their data quickly and easily.
===========================================================================
q240. Transforms (FFT, etc) and digital signal processing (DSP)
FFTs are a standard part of nearly every NA package.
For more info:
See the comp.dsp FAQ:
http://www.bdti.com/faq/dsp_faq.htm comp.dsp FAQ
Newsgroup: comp.dsp
See also:
Frigo and Johnson's library of FFT software:
http://www.fftw.org Frigo and Johnson's library
[author]:
FFTW is a C subroutine library for computing the Discrete Fourier Transform (DFT) in one or more dimensions, of both real and complex data, and of
arbitrary input size. We believe that FFTW, which is free software, should become the FFT library of choice for most applications. Our benchmarks,
performed on on a variety of platforms, show that FFTW's performance is typically superior to that of other publicly available FFT software. Moreover,
FFTW's performance is portable: the program will perform well on most architectures without modification.
It is difficult to summarize in a few words all the complexities that arise when testing many programs, and there is no "best" or "fastest" program.
However, FFTW appears to be the fastest program most of the time, especially in the multi-dimensional and real-complex cases (Kasparov is the best
chess player in the world even though he loses some games). Hence the name, "FFTW," which stands for the somewhat whimsical title of "Fastest
Fourier Transform in the West."
FFTW is free.
I am pleased to announce the release of pfftw-0.02, an experimental
fast Fourier transform library for the Pentium and Pentium MMX. pfftw
works for inputs whose size is a power of 2 less than or equal to
1024, and it produces an out-of-order output. This release of pfftw
supports both single and double precision. pfftw is completely
machine-generated, and it was optimized semi-automatically by
generating many different codes and selecting the fastest.
http://cr.yp.to/djbfft.html DJBFFT
[author]:
My FFT library is now tuned for both the Pentium and the UltraSPARC.
To give you an idea of how fast this is: Multiplying in R[x]/(x^256-1)
in double precision---two DFTs, scaling, multiplication, inverse DFT---
now takes about 14000 UltraSPARC cycles, or 20000 Pentium-II cycles, or
28000 Pentium cycles. I haven't done the roundoff analysis yet, but this
convolution should be enough for a product of two 2816-bit integers.
See also Dan Cross' page and FFT library:
http://www.intersrv.com/~dcross/fft.html Dan Cross' page
See also Joerg Arndt's page and his FFT library:
http://www.jjj.de/fft/fftpage.html FFT Stuff
http://www.jjj.de/fxt/ FXT
See also
Public domain FFT, and other numerical, code:
http://www.numis.nwu.edu/fft/ NWU
See also the FXT library:
http://www.jjj.de/fxt/ FXT
===========================================================================
q245. Wavelets
[Amara Graps] writes:
Wavelets are functions that satisfy certain mathematical requirements
and are used in representing data or other functions. They have
worked well as an alternative to fourier sine and cosine functions
in data analysis in many different scientific fields.
Some internet resources are:
Clemens Valens' wavelet tutorial and info
http://perso.wanadoo.fr/polyvalens/clemens/clemens.html Valens' Pages
Dept. of Mathematics at Salzburg University
http://www.cosy.sbg.ac.at/~uhl/wav.html Salzburg U. Mathematics Dept.
An extensive wavelet bibliography list can be found at Mathsoft:
http://www.mathsoft.com/wavelets.html Mathsoft
Amara Graps has a good wavelets page on the Web:
http://www.amara.com/current/wavelet.html Amara Graps' page
Also, she has an introductory paper at:
http://www.amara.com/IEEEwave/IEEEwavelet.html Amara Graps' paper
Clemens Valens has a good tutorial at:
http://perso.wanadoo.fr/polyvalens/clemens/clemens.html Valens' tutorial
http://paos.colorado.edu/research/wavelets/ A Practical Guide to Wavelet Analysis (.pdf, Fortran, IDL, Matlab)
LXP of the Internet Scout Report, at
http://scout.cs.wisc.edu/addserv/team.html Scout Report
wrote:
Researchers dealing with time series data will find this powerful
resource extremely helpful. Drs. Christopher Torrence (National
Center for Atmospheric Research) and Gilbert Compo (NOAA/ CIRES
Climate Diagnostics Center) have put together this Website for
researchers interested in using wavelet analysis, a technique that
decomposes a time series into time-frequency space. The site provides
information on "both the amplitude of any periodic signals within the
series, and how this amplitude varies with time." The nicely written
introductory section (Wavelet Analysis & Monte Carlo) is complete
with algorithms, graphically illustrated examples, and references
(including some links). First time users may wish to consult the
on-site article "A Practical Guide to Wavelet Analysis," originally
published in 1998 (.pdf format), or browse the FAQ section. The heart
of the site is the Interactive Wavelet Plots section; here, users may
experiment with wavelet analysis using time series data provided at
the site (i.e., Sea Surface Temperature, Sunspots) or provided by the
user. As if that weren't enough, the site also offers free Wavelet
software (Fortran, IDL, or Matlab; acknowledgment required) and
several abbreviated data sets for experimentation. [LXP]
Newsletters:
Wavelet Digest.
http://www.wavelet.org/wavelet/index.html Wavelet Digest.
===========================================================================
q250. Integration and Ordinary Differential Equations (ODEs)
Most of the general NA texts, such as Stoer & Bulirsch 1980, have chapters
on integration techniques.
See also:
Davis, Philip J.; Rabinowitz, Philip 1984
Methods of Numerical Integration
Academic Press, Orlando, Florida
ISBN 0122063600
ODEPACK, from netlib (see iii q115.1, "Netlib").
[Dave Linder]: Well known and widely used.
Allows error-based adaptive step-size control.
[author] A systematized collection of ODE solvers. Handles stiff and
nonstiff systems, sparse systems, explicit and linearly implicit
forms. Fortran IV, double precision. A single precision version
may be found in sodepack, also in netlib.
RKSUITE, from netlib ode/rksuite (see iii q115.1, "Netlib")
[Dave Lindner]: Also good. Allows error-based adaptive step-size control
and easy to use for explicit systems.
[author]: For initial value problem for first order ordinary
differential equations. A suite of codes for solving IVPs
in ODEs. A choice of RK methods is available. Includes an
error assessment facility and a sophisticated stiffness checker.
Template programs and example results provided.
Supersedes RKF45, DDERKF, D02PAF.
LSODE and DVODE, from netlib (see iii q115.1, "Netlib"):
[Jean Claude Boettner] The algorithm is the same but the jacobian
matrix is stored in DVODE allowing better efficiency, especially for big
systems of ODE (100-300 typically in my case). So expect a slow down (2 ?)
when using LSODE. It might be interesting to test VODEPK (on NETLIB)
with Krylov methods.
See also many other packages in the directory ode, in netlib.
Ernst/Wanner package:
ftp://ftp.unige.ch/pub/doc/math/ Ernst/Wanner
[author]: Separate Fortran codes for stiff, nonstiff, and mechanical systems.
For the description see the book by the authors:
Hairer, Ernst; Norsett; Wanner, Gerhard (1993): Solving Ordinary
Differential Equations. Nonstiff Problems. 2nd edition.
Springer Series in Comput. Math., vol. 8.
Phil Brubaker's ODEcalc:
http://www.mecheng.asme.org/database/EDU_TOOL/6186.html ODEcalc
[author]: It solves most
ODEs on a DOS 5.00+ (16 bit), 386+ PC. ODEcalc (tm) may be
downloaded from my website.
Other engineering programs are available.
ODE++
http://www.minet.uni-jena.de/www/fakultaet/iam/ode++/ ODE++
[author]: ODE++ is intended to deal with ordinary
differential equations.
At the moment, ODE++ contains classes for the representation of explicit
and linear-implicit ODE systems, for IVP and BVP parameters, and the
following IVP solvers: explicit Runge-Kutta-methods of order 5,6 and 8
as well as variable order multistep-methods of Adams-Moulton-type (order
1-12) and BDF-type (order 1-5).
SLDRIVER: Interactive Sturm-Liouville Package
ftp://ftp.rmcs.cranfield.ac.uk/pub/departments/seas/cised/numanal/ SLDRIVER
The classical Sturm-Liouville problem (SLP) is
(-p(x) y')' + q(x) y = lambda w(x) y (1)
where y is a real function of x on a real interval a ~100,000 nodes
do not run in a reasonable amount of time in our lab. If a
program cannot mesh a part within this limitation, I consider
it unable to mesh the part, even if it might successfully
generate the mesh. Automeshers should allow the specification
of a target number of nodes. Any mesh above this size should
send a flag to remesh, ignoring small features.
(d) Again, from a practical point of view, there are limits beyond which I
consider the program to fail. The most glaring comparison is
between PATRAN and MeshCAST. A typical part that meshes less
than 10 minutes with MeshCAST normally takes several days to
mesh in PATRAN. It is likely that given infinite time, PATRAN
would succeed (after all, it contains the RPI finite octree
mesher as one of its algorithms!), however, I can't justify
tying a machine up for a week to find out if it will mesh (and often it
crashes at the end of the meshing cycle!).
(e) There are many if's and's & but's here. Basically I use aspect ratio and
dihedral angle for tetrahedra, jacobian at the gauss points for hex'es,
wedge's, and quad's, and interior angle for triangles. These are the only
element types that I use.
(f) For many problems, I could not successfully mesh the part, so I sent the
geometry to the software vendor. In other cases, I sent it specifically
to evaluate the software run under the developer's care. Score reflects
willingness, speed, size, and quality of the mesh received.
(g) I am partial to a Mac-like interface, which I consider to be the computer
world's 'reference standard'. Program should require minimal training and
manuals. All options should be available on the menus (no hidden or
cryptic commands). This is not just personal preference, but time and
dollars in training.
(1) Cost is annual lease, US dollars, except as noted. Platform is HP-735
network license. Cost is what we pay, not necessarily list price.
(2) Unigraphics common database module $3,000 extra (i.e. $9,800). Base
license includes one translator, we chose IGES.
(3) This price includes the fluids, thermal, radiation, solver modules. I am
not sure of the price of just MeshCAST by itself.
(4) This is very approximated assuming infinite meshing time.
(5) Versions tested: OCTREE: March 1,1995, P3: v1.4, Meshcast: v3.0.3,
Hypermesh: v2.00b, Algor: July, 1995.
===================================
q260.5. PDE and FEM Software on the net
PDE and FEM Software on the net:
(See also iii q270, "Computational Geometry")
* iii q260.5.1, "FEMLAB"
* iii q260.5.2, "Fec"
* iii q260.5.3, "FElt"
* iii q260.5.4, "Femlib"
* iii q260.5.5, "Kaskade"
* iii q260.5.6, "Tri"
* iii q260.5.7, "QMG"
* iii q260.5.8, "Sinda/Fluint"
* iii q260.5.9, "Physica"
* iii q260.5.10, "Madpack5"
* iii q260.5.11, "Triangle"
* iii q260.5.12, "FreeFEM"
* iii q260.5.13, "Featflow"
* iii q260.5.14, "PLTMG"
* iii q260.5.16, "MUDPACK"
* iii q260.5.17, "METIS"
* iii q260.5.18, "ParMETIS"
* iii q260.5.19, "ParMETIS"
* iii q260.5.20, "Deal.II"
* iii q260.5.21, "PETSc"
* iii q260.5.22, "OFELI"
===================================
q260.5.1. FEMLAB
http://www.math.chalmers.se/Math/Research/Femlab/ FEMLAB
[author]: From the Department of mathematics at Chalmers
University of Technology and Gvteborg university.
FEMLAB is an interactive program for the numerical solution of
ordinary and partial differential equations based on the Finite
Element Method in adaptive form with automatic error control.
Femlab is a part of an educational program based on the Leibniz vision
of integration of Calculus, Computation and Application. The
educational program is presented in the texts:
Computational Differential Equations, Cambridge University Press ,
to appear 1996
Introduction to Adaptive Methods for Differential Equations, Acta
Numerica (1995) pp. 105-158.
===================================
q260.5.2. Fec
ftp://karazm.math.uh.edu/pub/Math Fec
A collection of finite element libraries in C++
===================================
q260.5.3. FElt
http://felt.sourceforge.net/ FElt
[author]:
FElt is a free system for introductory level finite element analysis. FElt
is intended largely as a teaching tool. At this stage it should be able
to handle most static and dynamic linear analysis problems (structural
and thermal) that you'd find in a one or two term introductory class in
finite element analysis; it also has some capabilities for modal and
spectral analysis. The FElt element library currently contains fifteen
elements ranging from a simple spring to an 8-node brick. The main
FElt applications are all built around a single intuitive, powerful,
and easy-to-use input syntax.
===================================
q260.5.4. Femlib
ftp://usc.edu/pub/C-numanal/femlib-1.1.tar.gz Femlib
Set of C++ classes for finite element work, garbage collection
algorithms, and sparse matrix algorithms. A bit rough; incomplete
in some areas.
===================================
q260.5.5. Kaskade
http://mgnet.ccs.uky.edu/mgnet/Codes/kaskade/ Kaskade
[author]:
The KASKADE 3.1 software package solves
linear scalar elliptic and parabolic problems in 1, 2, 3 space dimensions
with adaptive finite element methods.
Furthermore, the toolbox includes extensions for handling systems of
equations and example algorithms for nonlinear methods
used in obstacle, porous media or Stefan problems.
Core of the program is a variety og multilevel/multigrid preconditioners
for the arising linear systems.
This object-oriented code is written in C++ and can
be compiled with Gnu g++, version 2.7.2, and some other compilers.
If you want to compile with Gnu g++, version 2.6.3, you have to change
the definition of the complex-type in the file general.h.
The program solves the same mathematical problem classes as its predecessor
KASKADE 2.x, which is written in C.
We provided a graphical user interface ZGUI to the numerical program
based on the interface language Tcl/Tk of j. Ousterhout.
===================================
q260.5.6. Tri
ftp://ftp.cs.cornell.edu/pub/scott/tri Tri
[author]:
Tripoint was first developed by David Eppstein to triangulate point set
input in two dimensions, following the algorithm in "Provably Good Mesh
Generation" by Bern, Eppstein, and Gilbert[1]. During the summer of 1991,
Scott Mitchell extended the program to triangulate polygonal regions with
holes, again in two dimensions. The algorithm followed borrows ideas both
from [1] and "Quality Mesh Generation in Three Dimensions" by Mitchell
and Vavasis[2].
Tripoint takes input from text files as the polygon to triangulate. Output
is also as text files, using the same data format. Points are represented
by their coordinates, and edges by the indecies of their endpoints.
There is a matlab code front end, called drawmesh.m. This allows the
graphical input of the input polygon using the mouse, and the display with
zooming of the output triangulation. There is also matlab code called
dispmesh.m, which allows the displaying of output only. This allows the
user freedom over how to generate the input.
The algorithm is similar to one in "Provably
Good Mesh Generation"[1]. The main differences include: Tripoint uses
connected component information while generating the quadtree, as in [2].
Tripoint does not cut dangling acute triangles from the input as a first step
as in [1]. Ideally, as in [2], tripoint would center input verticies in
boxes, and use a very general and easy algorithm for triangulating
individual boxes. Instead, vertices are not centered, and
the ideal algorithm is used with added special case analysis for boxes near
an input vertex.
Scott Mitchell continues to support tripoint.
We would eventually like to implement a three dimentional algorithm
following [2].
===================================
q260.5.7. QMG
http://www.cs.cornell.edu/home/vavasis/qmg-home.html QMG
[author]:
QMG is free software
available on the Web for fully automatic unstructured finite element
mesh generation in two and three dimensions. It can generate meshes
for complex domains with curved boundaries and nonmanifold features.
QMG 2.0 can be run either from the shell, under Tcl/Tk (a freeware
scripting language) or Matlab. The Matlab version includes a simple
finite element solver. QMG is written in primarily in C++.
The main new feature of QMG2.0 (compared to QMG1.1) is its ability to
handle true curved geometry. QMG2.0 permits boundaries defined by
Bezier curves, triangular Bezier patches and quadrilateral
tensor-product Bezier patches. Representations of certain simple
curved geometries (cylinders, spheres, tori) using Bezier patches
are shipped with QMG.
===================================
q260.5.8. Sinda/Fluint
http://www.crtech.com Sinda/Fluint
[author]:
SINDA/FLUINT is a comprehensive finite-difference, lumped parameter
(circuit or network analogy) tool for analyzing complex thermal/fluid
systems. It is used at over 300 sites in the aerospace, electronics,
petrochemical, and automotive industries.
===================================
q260.5.9. Physica
http://www.gre.ac.uk/~physica/ Physica
A three dimensional unstructured mesh software
framework for the modelling of multi-physics phenomena.
===================================
q260.5.10. Madpack5
http://www.mgnet.org/mgnet/Codes/madpack5/ Madpack
[author]: Version 5 of Craig Douglas' multigrid package. This is an
abstract solver. It is PDE, domain, and discretization independent.
It only handles linear problems, however. It is an ongoing project
with a number of contributors from around the world. Some of these
wish to remain anonymous. Serial, parallel, and semi-chaotic solvers
are or will be included during 1994. A paper describing this is in
the file mgnet/papers/Douglas/mad5.ps. This is an object oriented code.
The user interface is written in C. Most of the solvers are
written in Fortran-77+m4. The same calling sequence is used
independent of the data's type (real and complex, single and double
precision are supported). The user interface builds all of the truly
nasty data structures needed by the code. The ownership of this
code is convoluted.
===================================
q260.5.11. Triangle
A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator.
http://www-2.cs.cmu.edu/~quake/triangle.html Mesh Generator
Triangle generates exact Delaunay triangulations, constrained Delaunay
triangulations, and quality conforming Delaunay triangulations. The
latter can be generated with no small angles, and are thus suitable
for finite element analysis.
===================================
q260.5.12. FreeFEM
http://augustine.mit.edu/~prudhomm/freefem.php3 FreeFEM
FreeFEM is a graphical software which is built around a programming
language dedicated to the partial differential equations.
FreeFEM solves,with the finite element method,scalar linear elliptic
PDEs of order 2,the time dependant equations and more generally all
iterative sheme with PDE combination for example the heat
equation,convection-diffusion and even the Navier-Stokes equations.The
program is written in C,it is shareware and portable.
Domains are defined by analytic equations of the boundary,and
triangulated by a Delaunay-Voronoi algorithm.
The language allows the manipulation of the complex numbers with the
reserved words I,Re,Im.
Systems of equations are also supported. Thus one can solve,for example
the problems of the linear elasticity.
===================================
q260.5.13. Featflow
http://gaia.iwr.uni-heidelberg.de/~featflow/ Featflow
[author]:
Our FEM software for incompressible Navier-Stokes equations, FEATFLOW1.0,
including all sources, manuals and many (!) demos for nonstationary flows
(as MPEG movies), is "downloadable" via Internet, see
===================================
q260.5.14. PLTMG
http://www.mgnet.org/mgnet-codes-pltmg.html PLTMG
PLTMG 8.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,
and features adaptive local mesh refinement, multigraph iteration,
and pseudo-arclength continuation options for parameter
dependencies. The package includes an initial mesh generator
and several graphics packages. Full documentation is provided in
PLTMG: A Software Package for Solving Elliptic Partial Differential Equations
- Users' Guide 8.0 (ISBN 0-89871-409-5), available from SIAM Publications.
PLTMG is provided as Fortran (and a little C) source code, in
both single and double precision versions. The included X-Windows GUI uses the
default Athena Widget set, and makes calls to standard library routines
of the X-Windows system, which must be loaded along with the PLTMG software.
PLTMG is available from Netlib and Mgnet.
===================================
q260.5.16. MUDPACK
http://www.scd.ucar.edu/css/software/mudpack/ MUDPACK
[author]:
MUDPACK includes a suite of portable fortran programs which automatically
discretize and use multigrid techniques to generate second- and fourth-order
approximations to elliptic Partial Differential Equations (PDEs) on
rectangular regions. The elliptic PDEs can be real or complex in two-
and three-dimensions with any combination of mixed derivate, specified, or
periodic boundary conditions. Multigrid V or W cycles which use point,
line(s), or planar relaxation and fully weighted residual restriction are
available for algorithm tuning to obtain optimal multigrid performance.
MUDPACK was written to avoid repeated "re-invention of the wheel" in human
code development time which can be at least as important as saving machine
cycles.
===================================
q260.5.17. METIS
http://www-users.cs.umn.edu/~metis/ METIS
http://www-users.cs.umn.edu/~karypis/metis/ METIS
[author]:
METIS is a Software Package for Partitioning Unstructured Graphs, Partitioning
Meshes, and Computing Fill-Reducing Orderings of Sparse Matrices.
Graph partitioning has extensive applications in many areas, including
scientific computing, VLSI design, and task scheduling. The problem is
to partition the vertices of a graph in k roughly equal parts, such that
the number of edges connecting vertices in different parts is minimized.
Graph partitioning is of particular importance in finite element
computations on parallel computers, since a good partition significantly
reduces the amount of communication, increasing the performance.
Graph partitioning algorithms are also used to compute orderings for
sparse matrices, in order to minimize the amount of fill and to increase
the concurrency that can be exploited during parallel direct
factorization.
METIS is a set of programs that implement various graph partitioning
algorithms
that are based on the multilevel paradigm. The advantages of METIS
compared to
other similar packages are the following:
- Provides high quality partitions!
Experiments on a large number of graphs arising in various domains
including
finite element methods, linear programming, VLSI, and transportation
show that
METIS produces partitions that are consistently better than those
produced
by other widely used algorithms. The partitions produced by METIS
are
consistently 10% to 50% better than those produced by spectral
partitioning
algorithms.
- It is extremely fast!
Experiments on a wide range of graphs has shown that METIS is one to
two
orders of magnitude faster than other widely used partitioning
algorithms.
Graphs with over 1,000,000 vertices can be partitioned in 256 parts
in under
20 seconds on a Pentium Pro personal computer.
- Provides low fill orderings!
The fill-orderings produced by METIS are significantly better than
those
produced by other widely used algorithms including multiple minimum
degree.
For many classes of problems arising in scientific computations and
linear
programming, METIS is able to reduce the storage and computational
requirements
of sparse matrix factorization, by up to an order of magnitude.
Moreover,
unlike multiple minimum degree, the elimination trees produced by
METIS are
suitable for parallel direct factorization. Furthermore, METIS is
able to
compute these orderings very fast. Matrices with over 200,000 rows
can be
reordered in just a few seconds on current generation workstations
and PCs.
===================================
q260.5.18. ParMETIS
http://www-users.cs.umn.edu/~karypis/metis ParMETIS
ParMETIS is a Parallel Graph Partitioning and Sparse Matrix Ordering Library.
ParMETIS is an MPI-based parallel library that implements a variety of
algorithms for partitioning unstructured graphs and for computing
fill-reducing orderings for sparse matrices. ParMETIS is particularly suited
for parallel numerical simulations involving large unstructured meshes.
For these computations, ParMETIS dramatically reduces the time spent in
communication by decomposing the mesh in a way that balances the load and
minimizes the number of interface elements.
===================================
q260.5.19. MODULEF
http://www-rocq.inria.fr/modulef/ MODULEF
[author]:
The MODULEF library contains about 3000 procedures written in Fortran 77. These procedures were designed with the utmost concern for software portability.
Automatic generation and modification of two- and three-dimensional meshes.
Specification of material characteristics or external forces by sub-domain or boundary section.
Choice of type of finite element method, for example, conforming, non-conforming, hybrid, or mixed. For non-conforming methods the flow and stresses can be
computed along with the temperature or displacement, or separately.
The finite element library contains about 36 elements for thermal analysis.
Linear systems can be solved using direct or iterative methods.
Solution methods for eigenproblems include inverse iteration, subspace iteration, Lanczos and QR methods.
Non-linear elasticity:
the solution of unilateral contact problems with or without friction by iterative algorithms,
the calculation of stresses in two- or three-dimensional elastoplasticity and the visualisation of plastic zones,
the calculation of large deformations of compressible or incompressible hyperelastic solids (two- or three-dimensional, or axisymmetric).
Solution of variational inequalities subject to bounded constraints by relaxation and complementarity.
Solution of the Dirichlet problem for a biharmonic operator by a mixed finite element method of order 1 or 2.
Calculation of velocities and pressure of a viscous incompressible fluid (Navier-Stokes equations).
The computation of homogenised coefficients of composite structures.
Decomposition of domains.
Calculation of stresses and interpretation of results.
Several modules are available for the display of results, interactively or in batch, for example to plot two- or three-dimensional meshes, deformations, stresses,
isovalues, velocities and streamlines in fluid mechanics, etc.
===================================
q260.5.20. Deal.II
http://gaia.iwr.uni-heidelberg.de/~deal/ deal.II
[author]:
deal.II is a C++ class library targeted at adaptive finite elements.
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 locally refined meshes and
enables you to use a variety of finite elements in one, two, and three
space dimensions, as well as support for time-dependent problems.
The library is written for research purposes and offers many features:
- Support for one, two, and three space dimensions, using a unified
interface that enables writing 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, and discontinuous 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 about 250 pages of tutorials, several
reports, and far more than 1,000 pages of programming interface
documentation with explanations of all classes, functions, and
variables.
- 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.
- Support for several output formats, including some common formats
for visualization of scientific data.
- Support for a variety of computer platforms, including multi-
processor machines.
- Free source code under an Open Source license for noncommercial
purposes, and the invitation to contribute to further development of
the library.
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 support for time-dependent problems.
===================================
q260.5.21. PETSc
http://www.mcs.anl.gov/petsc PETSc
PETSc is a set of libraries for the implicit solution of PDEs and related
problems. New features of this release include:
(1) a parallel, sparse, symmetric matrix storage format, this includes
support for sequential Cholesky and ICC(k)
(2) a complete framework for parallel linear multigrid on
structured grids (for both linear and nonlinear problems)
(3) Mandel's balancing Neumann-Neumann method for scalar PDEs
(4) an interface to the Tufo-Fischer highly efficient parallel
coarse grid direct solver library tfs
(5) support for managing "composite" vectors consisting of
subvectors that represent conceptually different quantities
(for example, constraints or Lagrange multipliers)
(6) more complete hypertext documentation, including links to
hypertext versions of all the examples and source code
===================================
q260.5.22. OFELI
http://wwwlma.univ-bpclermont.fr/~touzani/ofeli.html OFELI
OFELI (Object Finite Element LIbrary) is a library (or a toolkit) of C++
classes to build up finite element codes. The package contains numerous simple
and less simple examples of finite element codes using OFELI. A significant
documentation (html and pdf formats) is provided.
===================================
q260.6. Commercial Packages for FEM
A large list of commercial FEM products may be found at:
http://www.cray.com/PUBLIC/APPS/DAS/DAS4.html List of FEM Products
===========================================================================
q265. Operations Research: Minimization, Optimization, Etc.
* iii q265.1, "Optimization, Linear and Non-Linear Programming: General Resources"
* iii q265.2, "Optimization, Linear and Non-Linear Programming: References"
===================================
q265.1. Optimization, Linear and Non-Linear Programming: General Resources
See the FAQs maintained by Robert Fourer and John Gregory:
http://www.mcs.anl.gov/home/otc/Guide/faq/ LP and NLP FAQs
See also:
Decision Tree for Optimization Software
by Hans D. Mittelmann, Dept of Mathematics, Arizona State U.,
and P. Spellucci, Dept of Mathematics, Technical U. Darmstadt.
http://plato.la.asu.edu/guide.html Decision Tree for Optimization Software
KachinaTech Optimization Index
http://SAL.KachinaTech.COM/B/3/ KachinaTech
NEOS Optimization Server
http://neos.mcs.anl.gov/ NEOS
An online optimization server.
[author]:
Our optimization solvers represent the state-of-the-art in optimization software. Optimization problems are solved automatically with minimal input from the user. Users only need a definition of the optimization problem; all additional information required by the optimization solver is determined automatically.
By the OTC, a joint effort of Argonne National Laboratory
and Northwestern University.
The Optimization Technology Center at Argonne National Laboratory (ANL).
http://www.mcs.anl.gov/home/otc/ ANL Optimization Center
Arnold Neumaier's overview:
http://solon.cma.univie.ac.at/~neum/glopt.html Neumaier
Simon Streltsov's pages:
http://cad.bu.edu/go/ Streltsov
Michael Trick's Operations Research Page
http://mat.gsia.cmu.edu/ Michael Trick
Semidefinite programming:
http://cs.nyu.edu/cs/faculty/overton/sdppack/sdppack.html SDPpack
We would like to announce a new version of our code
SDPpack (Version 0.9 Beta for Matlab 5.0). This version
extends the previous release for semidefinite programming (SDP)
to mixed semidefinite-quadratic-linear programs (SQLP), i.e.
linear optimization problems over a product of semidefinite cones,
quadratic cones and the nonnegative orthant.
The OpsResearch Links Page:
http://opsresearch.com/OR-Links/index.html OpsResearch
A nice collection of links for optimization and simulation.
Composite Concave Linear Programming
http://www.ms.unimelb.edu.au/~moshe/cclp/what.html CCLP-LAND
CCLP is an extension of linear programming allowing a broad class
non-linear objective functions. However, the constraints must
remain linear.
SolvOpt
http://www.uni-graz.at/imawww/kuntsevich/solvopt/ SolvOpt
[author]:
SolvOpt is a collection of the M-files for use with Matlab,
FORTRAN and C source codes.
SolvOpt (Solver for local optimization problems) is concerned with
minimization or maximization of nonlinear, possibly non-smooth objective
functions and solution of nonlinear minimization problems taking into account
constraints by the method of exact penalization.
SolvOpt is a freeware and comes with no warranty.
IMPS optimization utilities:
ANALYZE (computer-assisted analysis),
MODLER ( modeling language), and
RANDMOD (randomizing instances for experimentation).
http://www.cudenver.edu/~hgreenbe/imps/imps.html IMPS
John Chinneck's MProbe
http://www.sce.carleton.ca/faculty/chinneck/mprobe.html MProbe
MProbe is a software tool for analyzing mathematical programming models. It has special capabilities for
analyzing nonlinear functions to discern their shapes in a region of interest (i.e. whether the function is
linear or almost linear, convex or almost convex, concave or almost concave, or concave and convex).
Knowledge of function shape is crucial when developing nonlinear optimization models, or when selecting
the nonlinear solver for a nonlinear optimization problem. Determining function shape is difficult for
nonlinear functions having more than two variables. MProbe is specifically designed to operate on nonlinear
functions having many variables. MProbe also estimates the shape of a nonlinearly constrained region
(convex? nonconvex?), the objective function effect (global optimum? local optimum only?), and the
effectiveness of the constraints.
ftp://plato.la.asu.edu/pub/donlp2/donlp2_td.tar.gz Automatic Diff NLP
http://plato.la.asu.edu/donlp2.html Automatic Diff NLP
A new Automatic Differentiation version of Peter Spellucci's
NLP package DONLP2 has been
released. It uses the TAMC utility of Ralf Giering.
AMPL (Commercial package)
http://www.ampl.com/cm/cs/what/ampl/key.html AMPL
[author]: AMPL is a comprehensive and powerful algebraic modeling language for linear and nonlinear optimization
problems, in discrete or continuous variables.
Developed at Bell Laboratories, AMPL lets you use common notation and familiar concepts to formulate
optimization models and examine solutions, while the computer manages communication with an
appropriate solver.
AMPL's flexibility and convenience render it ideal for rapid prototyping and model development, while its
speed and control options make it an especially efficient choice for repeated production runs.
MINOPT (Commercial package)
http://titan.princeton.edu/MINOPT/ MINOPT
[author]:
MINOPT is a comprehensive, powerful, and flexible package for the
solution of various types of optimization problems. It features both
an ADVANCED MODELING LANGUAGE for the clear and concise representation
of complex mathematical models as well as a ROBUST ALGORITHMIC
FRAMEWORK for the efficient solution of wide variety of mathematical
programming problems.
APPSPACK
http://csmr.ca.sandia.gov/projects/apps.html APPSPACK
[author]:
APPSPACK is the implementation of an asynchronous and fault tolerant
parallel pattern search method for unconstrained or bound constrained
optimization. Pattern search uses only function values for
optimization, so it can be applied to a wide variety of problems, such
as engineering optimization design problems characterized by a small
number of variables and by expensive objective function evaluations
(typically complex simulations that take minutes or hours to
run). Parallelism is achieved by dividing the search directions and
corresponding function evaluations among the different processors. The
asynchronicity is due to the fact that the search along each direction
continues without waiting for searches along other directions to
finish, in contrast to the standard parallel pattern search
method. Further, APPS is also fault tolerant so it is not hindered by
node failures. APPSPACK uses either PVM or MPI for parallel
communications, and it can also be run serially.
SBmethod
http://www.mathematik.uni-kl.de/~helmberg/SBmethod/ SBmethod
[author]:
SBmethod is a C++ code for large scale eigenvalue optimization.
SBmethod implements the spectral bundle method for minimizing
the maximum eigenvalue of an affine matrix function (real and
symmetric). The code is intended for large scale problems. It
supports sign constraints on the design variables and allows
to exploit structural properties of the matrices such as
sparsity and low rank structure.
Galahad
http://galahad.rl.ac.uk/galahad-www/ Galahad
[author]:
Galahad is a library
of thread-safe Fortran 90 packages for large-scale nonlinear
optimization. GALAHAD includes two packages for nonconvex quadratic
programming (one being interior-point based, the other is of the
active/working set variety), a quadratic programming preprocessing
package, an updated version of LANCELOT, and a number of other
subsidiary optimization-related tools. Full PostScript and PDF
documentation is included, as are installation scripts for a variety
of Unix-like platforms.
===================================
q265.2. Optimization, Linear and Non-Linear Programming: References
Here are only a few popular and/or new references. It's a huge
field! See also
iii q265.1, "Optimization, Linear and Non-Linear Programming Resources"
Chvatal, Vasek, 1983
Linear Programming
W.H. Freeman
A current classic for graduate and upper level undergraduate courses.
Stephen J. Wright
Primal-dual Interior-point Methods
Siam 1997 / xx+289 pages / Softcover / ISBN 0-89871-382-X / Order Code OT54
For more information see
http://www.siam.org/books/swright/ Wright
Robert J. Vanderbei
Linear Programming: Foundations and Extensions
Kluwer Academic Publishers, Boston
Hardbound, ISBN 0-7923-9804-1
September 1996, 440 pp.
NLG 240.00 USD 129.95 GBP 92.50
This book is an introductory graduate textbook on linear programming
although upper-level graduate students and researchers will find plenty of
material here that cannot be found in other books. It has also been used
successfully to teach undergraduates majoring in Operations Research.
Balanced treatment of the simplex method and interior-point methods.
Efficient source code (in C) for all the algorithms presented in the text,
available from:
http://www.princeton.edu/~rvdb/ Vanderbei
Stephen G. Nash and Ariela Sofer
Linear and Nonlinear Programming
McGraw-Hill (1996)
ISBN: 0-07-046065-5 See:
Tam\'as Terlaky (Ed.)
Interior Point Methods of Mathematical Programming
Kluwer Academic Publishers (September 1996)
ISBN 0-7923-4201-1
This book primarily intends to give an introduction to the theory of
Interior Point Methods (IPMs) in Mathematical Programming.
At the same time we try to give a quick overview of the
impact, of the extensions of IPMs to smooth nonlinear optimization
and to give an impression of the potentials of IPMs in solving
difficult practical problems.
Practical Methods of Optimization
R. Fletcher
John Wiley, 1987
Excellent practical text on non-linear programming.
J.E. Dennis Jr. and R.B. Schnabel
Numerical Methods for Nonlinear Optimization and Nonlinear Equations
Siam, 1983
Gill, Murray and Wright
2 volume book on Nonlinear Programming.
K.G.Murty, 1988
Linear Complementarity, Linear and Nonlinear Programming
Heldermann Verlag
Bazraa and Shetty.
Nonlinear Programming, theory and algorithms,
Luenberger:
Linear and Nonlinear Programming
Yair Censor and Stavros A. Zenios, 1997
Parallel Optimization: Theory, Algorithms, and Applications
Oxford University Press, New York, 1997.
C. Roos, T. Terlaky and J.-Ph. Vial. 1997
Theory and Algorithms for Linear Optimization: An Interior Point Approach
John Wiley, Chichester, 1997.
http://ssor.twi.tudelft.nl/Publications/Books/TAfLOAIPM/ipmbook.html I.P. Optimization
Stephen J. Wright 1997
Primal-Dual Interior-Point Methods
SIAM 1997 / xx+289 pages / Softcover / ISBN 0-89871-382-X
http://www.siam.org/books/swright/ SIAM
[author]:
In the past decade, primal-dual algorithms have emerged as the most
important and useful algorithms from the interior-point class. This
book presents the major primal-dual algorithms for linear programming
in straightforward terms. A thorough description of the theoretical
properties of these methods is given, as are a discussion of practical
and computational aspects and a summary of current software.
===========================================================================
q267. Queueing Theory and Performance Analysis.
The only thing close to a FAQ is at:
ftp://rtfm.mit.edu/pub/usenet-by-group/comp.benchmarks/ comp.benchmarks FAQ
References:
By far the most often referenced works are the classics by Kleinrock:
Kleinrock, Leonard 1975
Queueing Systems, Volumes 1 and 2
John Wiley, New York
Excellent theoretical development of the field. This is
the standard text in the area. Kleinrock is apparently
working on an updated version of his texts, but when
they'll be published is unknown.
Other good texts are:
Allen, Arnold O. 1990
Probability, Statistics, and Queueing Theory with Computer
Science Applications, Second Edition
Academic Press, Boston.
This is a common text in the field and has an applied approach.
King, Peter J. 1990.
Computer and Communication Systems Performance Modelling
Prentice Hall
Brief intro to prob theory,
MG1, priority queues, networks of queues, approximations.
Also chapters on numerical solutions, local area networks.
Nelson, Randolph. 1995.
Probability, stochastic processes, and queueing theory
Springer Verlag
Good treatment of prob, combinatorics, RVs and some distributions ...
but only uniform, binomial, exponential, poisson. Not the normal
distribution! Also, expectation, a big treatment of MG1, markov processes,
matrix geometric solutions, and queueing networks.
Perros, Harry G. 1995.
Queueing Networks with Blocking.
Oxford press
Brings together many results for different
types of blocking. Blocking occurs when server i cannot
continue serving because the queue at server j is full.
===================================
Queueing Theory and Performance Newsgroups
sci.op-research
sci.math.num-analysis
===================================
Queueing Theory and Performance Indices
Decision Tree for Optimization Software
by Hans D. Mittelmann, Dept of Mathematics, Arizona State U.,
and P. Spellucci, Dept of Mathematics, Technical U. Darmstadt.
http://plato.la.asu.edu/guide.html Decision Tree for Optimization Software
===========================================================================
q270. Computational Geometry
Directory of Computational Geometry Software
http://www.geom.umn.edu/software/cglist/ Computational Geometry Directory
This page contains a list of free computational geometry programs and
packages.
See also iii q260, "Partial Differential Equations (PDEs) and Finite Element Modeling (FEM)".
===========================================================================
q275. Interval Arithmetic
A good starting place is:
http://www.cs.utep.edu/interval-comp/ Interval Computations
===========================================================================
q285. Plotting, Graphics and Scientific Visualization
This is a huge field. Rather than attempt to review it,
I've simply noted a few resources. All text is [author].
* iii q285.1, "NASA Index on Scientific Visualization"
* iii q285.2, "Other Web Sites on Graphics and Sci Vis"
* iii q285.3, "Software for Plotting, Graphics and Sci Vis"
===================================
q285.1. NASA Index on Scientific Visualization
The best resource I found is an annotated list of
scientific visualization sites, courtesy of
NASA's Numerical Aerodynamic Simulation program.
http://www.nas.nasa.gov/Groups/VisTech/visWeblets.html NASA Graphics Index
Excerpting from [NASA], some of the large general purpose scientific
visualization web sites are: (Thanks NASA!)
Graphics, Visualization, and Usability Center at Georgia Tech.
This extensive web site includes scivis work along with material
from related fields such as animation, virtual environments,
medical informatics, software visualization, user interface
software, multimedia, educational technology, human factors, and
hypertext. Plenty of content here.
http://www.cc.gatech.edu/gvu/gvutop.html Georgia Tech
MIT Aero/Astro Scientific Visualization This web site is home to
Visual2, Visual3, and pV3. These are visualization systems for
unsteady, unstructured (and structured) CFD visualization
(mostly). Visual2 is for 2D flows, Visual3 for 3D flows, and pV3
takes data from solvers on distributed workstations on the fly.
There are papers, software, and users manuals. The author assures
me that pictures will be coming. The software is binary and
libraries only, not source code.
http://raphael.mit.edu/haimes.html MIT
The University of Minnesota Supercomputing Institute. This
web site contains pointers to URLs of interest to the
scientific visualization community.
http://web.msi.umn.edu U. Minnesota Superconducting
The Geometry Center, University of Minnesota. This excellent
web site contains examples of, software for, and technical
and other information about some of the premier mathematical
visualizations on the planet.
http://www.geom.umn.edu/ U. Minnesota Geometry Center
A Gallery of Interactive On-Line Geometry The Geometry Center
also has an incredible page with links to their interactive,
web-based, visualizations of various mathematical objects.
Interaction is slow due to the network, but these forms-based
programs are well worth looking at.
http://www.geom.umn.edu/apps/gallery.html U. Minnesota Geometry Center
State University of New York at Stony Brook has a very nice web
site with excellent information about their program which is
primarily centered around the VolVis software. The source and
executables are available along with many full papers in
compressed PostScript format.
http://www.cs.sunysb.edu/~volvis/ State U. of NY at Stony Brook
Stanford Computer Graphics Laboratory. Good projects, pictures,
movies, software, technical papers and descriptions of some of the
graphics work at Stanford University.
http://www-graphics.stanford.edu/ Stanford Computer Graphics Lab
CRS4: Centre for Advanced Studies Research and Development in
Sardinia (Cagliari, Italy). This extensive web site contains
pictures, movies, projects, staff, research papers, and
hypertextual MPEG info. A few papers are in Italian, but most of
the web site is in English.
http://www.crs4.it/~zip/group_homepage.html CRS4
Lawrence Livermore National Laboratory's web site has lots of
images, papers, and some software. Lots of interesting
visualization techniques here!
http://www.llnl.gov/graphics/sciviz.html LLNL
The National Center for Supercomputing Applications (NCSA)
NCSA Visualization and Virtual Environments page . This
extensive web site contains pictures, movies, descriptive
text, and research papers. Visualization work covers a wide
variety of application areas.
http://www.ncsa.uiuc.edu/ NCSA
NCSA Digital Information Systems Overview contains many
visualizations.
http://archive.ncsa.uiuc.edu/SCMS/DigLib/text/overview.html NCSA visualizations.
ftp://ftp.ncsa.uiuc.edu NCSA
NCSA Virtual Reality Lab briefly describes some VR projects
including some scientific visualization. There are also some
research papers.
http://www.ncsa.uiuc.edu/Viz/VR/VRHomePage.html NCSA VR lab
ftp://ftp.ncsa.uiuc.edu NCSA VR lab via ftp
NASA's Numerical Aerodynamic Simulation Division (NAS)
http://www.nas.nasa.gov/home.html NASA's NAS
The Army High Performance Computing Research Center. This web site
contains a variety of pictures, movies, software, etc.
http://www.arc.umn.edu/ Army
Other good web sites are:
http://stommel.tamu.edu/~baum/ocean_graphics.html S. Baum: Software for Graphics and Data Analysis
===================================
q285.2. Other Web Sites on Graphics and Sci Vis
For more general graphics questions, less related to
scientific visualization:
See the several FAQs relating to computer graphics:
http://www.faqs.org/faqs/graphics/ faqs.org
See the comp.graphics.misc FAQ:
http://www.primenet.com/~grieggs/cg_faq.html Grieggs
ftp://rtfm.mit.edu/pub/usenet/news.answers/graphics/faq comp.graphics.misc FAQ
An overview of computer graphics is at
LS VII, Computer Graphics, in the Department of Computer
Science at the University of Dortmund.
http://ls7-www.cs.uni-dortmund.de/cgotn/ LS VII
For commercial software, see the following sites:
http://www.cray.com/PUBLIC/APPS/DAS/DAS8.html Cray
The UIUC Visualization, Media and Imaginge Lab
http://www.itg.uiuc.edu/vmil/ UIUC VMIL
===================================
q285.3. Software for Plotting, Graphics and Sci Vis
The most common free software package is gnuplot:
ftp://ftp.dartmouth.edu/pub/gnuplot gnuplot
Another common one is plotutils, from GNU:
ftp://prep.ai.mit.edu/pub/gnu/plotutils Gnu Archives
Another excellent package is Dan Kelley's GRI:
http://gri.sourceforge.net/ Kelley's GRI
jsplot is a mixture of a technical plotting tool and a
simple drawing and presentation graphics program. It runs on UNIX using
X11/Motif and on Windows.
http://ourworld.compuserve.com/homepages/jsieberer/ jsplot
Also see:
http://plasma-gate.weizmann.ac.il/Grace/ Grace
Grace is a WYSIWYG 2D plotting tool for the X Window System and M*tif.
Grace runs on practically any version of Unix. As well, it has been
successfully ported to VMS, OS/2 and Win9*/NT (some minor functionality
may be missing, though).
http://www.astro.caltech.edu/~tjp/pgplot/index.html PGPLOT
[author]:
The PGPLOT Graphics Subroutine Library is a Fortran- or C-callable,
device-independent graphics package for making simple scientific
graphs. It is intended for making graphical images of publication quality
with minimum effort on the part of the user. For most applications, the
program can be device-independent, and the output can be directed to the
appropriate device at run time.
The PGPLOT library consists of two major parts: a device-independent part
and a set of device-dependent ``device handler'' subroutines for
output on various terminals, image displays, dot-matrix printers, laser
printers, and pen plotters. Common file formats supported include
PostScript and GIF.
PGPLOT itself is written mostly in standard Fortran-77, with a few
non-standard, system-dependent subroutines. PGPLOT subroutines can
be called directly from a Fortran-77 or Fortran-90 program. A C binding
library (cpgplot) and header file (cpgplot.h) are provided that
allow PGPLOT to be called from a C or C++ program; the binding library
handles conversion between C and Fortran argument-passing
conventions.
PGPLOT has been tested with UNIX (most varieties, including Linux, SunOS,
Solaris, HPUX, AIX, and Irix) and OpenVMS operating
systems. I am unable to provide support for DOS, Windows, Windows/NT, or
MacOS, but I do distribute code provided by users for use
with these operating systems.
For commercial software, see iii q125, "Commercial Packages",
and iii q520, "Symbolic Algebra".
Also see:
ftp://ftp.x.org/contrib/applications/Plotmtv1.4.1.tar.Z Plotmt for Unix
Also see:
http://www.alphaWorks.ibm.com/formula/CViz CViz
[author]:
CViz is a visualization tool designed for analyzing
high-dimensional data in large,
complex data sets. This tool is very useful for analysts who often use
statistical methods.
Also see iii q285.2, "Other Web Sites".
===========================================================================
q290. Miscellaneous NA Software
http://www.nrao.edu/ NRAO
http://www.cv.nrao.edu/aips/ NRAO AIPS
The National Radio Astronomy Observatory Astronomical Image Processing
System is a software package for calibration, data analysis,
image display, plotting, and a variety of ancillary tasks on Astronomical
Data. It comes from the National Radio Astronomy Observatory. It is primarily for Radio Astronomy. There is a Usenet newsgroup alt.sci.astro.aips that
deals with AIPS issues and has occasional interesting announcements. There is a FAQ (answers to Frequently Asked Questions) for this newsgroup too.
http://www.bsp-worldwide.org/implmnts/oxtool/ Oxford BSP Toolset
Oxford BSPlib
[author] Parallel programmers looking for a simple but efficient approach to
developing scalable applications software may be interested in the new
BSPlib programming library. BSPlib is an alternative to MPI and PVM, and is
based on the BSP model of parallel computation. It is already being used by
a rapidly growing community of software developers in universities and in
industry.
The BSP approach to parallel programming is applicable to all kinds of
parallel architecture: distributed memory machines, shared memory
multiprocessors, and networks of workstations. It provides a consistent,
and very general, framework within which to develop portable parallel
software for scalable architectures. One particular advantage of BSP is
that it provides _predictable_ high performance.
BSPlib can be used with C or Fortran. It supports SPMD parallelism based on
efficient one-sided communications. The core library (excluding collective
communications) consists of just 20 primitives.
The final BSPlib Definition (with C or Fortran Examples) can be obtained
from any one of the WWW sites listed below. Information on implementations
and their availability will be posted to this newsgroup in the next few days.
http://icl.cs.utk.edu/netsolve/ NetSolve
NetSolve is a software environment for network computing that combines
distributed computational resources into a unified service for solving
complex scientific problems remotely. Using a client-agent-server
paradigm, it aggregates the hardware and software resources of any
number of computers that are loosely connected across a network and
offers up their collective power through client interfaces that are
familiar from the world of uniprocessor computing. When a user wants a
certain computational task performed, he or she can use any one of a
number of conventional software clients (e.g. MATLAB, Mathematica,
simple procedure calls) to contact an agent with the request. The agent
keeps track of information about all the servers in its resource pool,
including their availability, load, network accessibility, and the range
of computational tasks they can perform. The agent then selects a server
to perform the task, and the server responds to the client's request. A
load-balancing policy is used to manage computational resources to
ensure good performance and simple retry provides fault-tolerance.
===========================================================================
q505. Probability and Statistics
* iii q505.1, "Probability and Statistics Books"
* iii q505.2, "Probability and Statistics Newsgroups"
* iii q505.3, "Probability and Statistics Websites and Indices"
* iii q505.4, "Probability and Statistics Software"
See also:
* iii q205, "Dense (Non-Sparse) Linear Algebra Systems"
* iii q115.3, "Statlib"
===================================
q505.1. Probability and Statistics Books
There are hundreds of prob/stat texts, but I'm
interested in the marriage of statistics and computing:
Thisted, Ronald A. 1986
Elements of statistical computing: numerical computation
Chapman and Hall, New York
A good text, and inexpensive. [Allen Mcintosh]
Griffiths, Paul; Hill, Ian David, editors. 1985
Applied statistics algorithms
E. Horwood Publishing, Chichester, England
Algorithms are available on statlib.
Moshier, Stephen Lloyd Baluk. 1989
Methods and programs for mathematical functions
E. Horwood Publishing, Chichester, England
Halsted Press, New York.
Trivedi, Kishor Shridharbhai 2001
Probability and Statistics with Reliability, Queuing, and Computer Science Applications (The Blue Book)
Prentice-Hall, Englewood Cliffs, NJ
ISBN number 0-471-33341-7.
Out of print; see:
http://www.ee.duke.edu/~kst/ Trivedi
Kennedy, W. J.; Gentle, J. E. 1980
Statistical Computing
Dekker, New York
others?
===================================
q505.2. Probability and Statistics Newsgroups
sci.stat.consult
sci.stat.edu
sci.stat.math
===================================
q505.3. Probability and Statistics Websites and Indices
Statistics and Statistical Graphics Resources, by York University
http://www.math.yorku.ca/SCS/StatResource.html York U.
Contents:
General statistical resources || York stuff || Statistical
Associations || Statistics Departments || SAS stuff || SPSS ||
LispStat || S Plus || Mathematica || Data Visualization & Statistical
Graphics || Psychology & Psychometrics || Online courses || New Online
WWW statistics || Data || New Categorical Data Analysis || New Other
Statistical Packages || New Unix
http://www.statserv.com/ St@tServ
Large search engine for free and commercial statistics resources.
http://www.stata.com/links/stat_software.html Stata links
Large list of free and commercial statistics resources.
===================================
q505.4. Probability and Statistics Software
Statistical Services Software Sites
http://www.utexas.edu/cc/stat/world/softwaresites.html U. Texas
Pointers to various commercial and free packages.
StatLib, by the Carnegie Mellon University Statistics Department.
see iii q115.3, "Statlib".
University of Minnesota School of Statistics
http://www.stat.umn.edu/ARCHIVES/archives.html U. Minnesota
Archives for Xlisp-Stat, MacAnova, R-Code.
Alan Miller's Page:
http://members.ozemail.com.au/~milleraj/ Alan Miller
A collection of code for statistical use.
This code is in Fortran 90, and
includes random number generation, least squares including both
non-linear and non-negative (linear) least squares, and the
evaluation of some common distribution functions.
Xlisp-Stat Resources
http://lib.stat.cmu.edu/xlispstat/ CMU XlispStat Archive (Alternate site for Xlisp-Stat)
Xlisp-Stat Information Xlisp-Stat is an object oriented environment
for statistical computing and dynamic graphics. Written by Professor
Luke Tierney (School of Statistics, University of Minnesota),
Xlisp-Stat was motivated by the "S" system, with the basic principal
that an extendible system is necessary for researching new
computationally based statistical methods. Xlisp-Stat provides a set
of high-level tools to develop new dynamic graphics techniques, such
as those found in the R-code.
Unlike S, Xlisp-Stat is based on Lisp, a well-established, complete
and flexible programming language. Like S, Xlisp-Stat is an
interpreted language, which is much more suited towards exploration
than a compiled language (such as C/C++ or Pascal -- these require
lengthy recompilations to fix bugs or test simple new ideas). When
greater speed is required, a byte-code compiler can be run from inside
Xlisp-Stat. This compiler can give increase the speed of execution by
an order of magnitude.
The defining reference book on Xlisp-Stat is Lisp-Stat by Luke
Tierney, 1990, J. Wiley and Sons, ISBN 0-471-50916-7. Since Xlisp-Stat
is founded on Lisp, almost any book on general Lisp programming can
help you get started.
Ox, by Jurgen A. Doornik
http://www.nuff.ox.ac.uk/Users/Doornik/ Ox
Ox is an object oriented matrix programming language, with a C and C++
like syntax. Ox currently has versions for Windows (PC and Alpha),
MS-DOS, Linux, SunOS, Solaris and HP-UX.
Packages include: Estimation and forecasting of ARFIMA(p,d,q)
and ARMA(p,q) models; QuadPack is a Fortran library for
univariate numerical integration (`quadrature') using adaptive rules
SSFPack is a package for analysing univariate Gaussian and
non-Gaussian time series which can be placed in the state space
form (SSF); MaxBFGS() can be used to maximize
functions of many parameters such as likelihood functions;
The PcFiml class contains code for VARs,
cointegration, simultaneous equations estimation, (multivariate)
diagnostic tests; the Simulation class allows for easy
implementation of simulation experiments. Some examples are in
ox/samples/simula.
U. Texas Dept of Biomathematics software.
This is mostly Fortran, but some is also in C. DCDFLIB is a
good set of functions for computing cumulative distribution
function values.
http://odin.mdacc.tmc.edu/anonftp/ U. Texas Biomath via www
ftp://odin.mdacc.tmc.edu/pub/index U. Texas Biomath via ftp
Other resources:
Simstat web site:
http//www.simstat.com/ Simstat
See also dense linear algebra packages, like
C.R. Birchenhall's MatClass, at:
iii q205, "Dense (Non-Sparse) Linear Algebra Systems"
Gary Perlman's C program for a Normal, Chi-square, and F distributions:
ftp://www.netlib.org/a/perlman Perlman
http://www.nag.com NAG
NAG (Numercal Algorithms Group) has an extensive library
http://www.componentsource.com componentsource.com
A component and add in reseller. There are several (and you can try them out).
http://www.spss.com SPSS
If you use SPSS you can also call their DLL's for all kinds of functions and
embed your calculations in their software.
http://shazam.econ.ubc.ca/ SHAZAM econometrics package
[D. Guiles]: I have found the new Windows
version to be really well received by my students. (c) SHAZAM is specially
"econometrics-oriented" - it is always up to date in terms of the
tests/estimators that are spcifically of interest to econometricians.
http://www.mathsoft.com/ S-PLUS
Large Windows-based commercial package.
===========================================================================
q510. Chaos Theory (Nonlinear Dynamics)
* iii q510.1, "FAQs for Chaos Theory"
* iii q510.2, "Newsletters for Chaos Theory"
* iii q510.3, "Bibliography for Chaos Theory"
q510.1. FAQs for Chaos Theory
http://amath.colorado.edu/appm/faculty/jdm/faq.html FAQ
http://www.enm.bris.ac.uk/research/nonlinear/faq.html FAQ
http://amath.colorado.edu/appm/faculty/jdm/faq.html FAQ
ftp://rtfm.mit.edu/pub/usenet/news.answers/sci/nonlinear-faq FAQ
See also:
http://www.drchaos.net/drchaos/intro.html Chaos Misc
===================================
q510.2. Newsletters for Chaos Theory
UK Nonlinear News
The primary goal of UK Nonlinear News is to allow researchers in the
applied and theoretical sides of nonlinear mathematics to keep
abreast of the wide variety of nonlinear activities throughout the UK.
To join the mailing list, send email to uk-nonl-subs@ucl.ac.uk
with the word SUBSCRIBE in the subject field.
Or see:
http://www.amsta.leeds.ac.uk/Applied/news.dir/index.html Nonlinear News
===================================
q510.3. Bibliography for Chaos Theory
Peter E. Beckmann (beckmann@nemo.physik.uni-mainz.de) at the
Department of Physics, University of Mainz, Mainz, Germany has a
nonlinear papers bibliography containing thousands of entries.
http://www.uni-mainz.de/FB/Physik/Chaos/chaosbib.html Nonlinear biblio
ftp://ftp.uni-mainz.de/pub/chaos/chaosbib Nonlinear biblio, BibTex-style
ftp://ftp.uni-mainz.de/pub/chaos/chaosref Nonlinear biblio, Refs-style
===========================================================================
q520. Symbolic Algebra
Since the symbolic algebra systems have been well documented
elsewhere, I simply provide pointers instead of reviewing
them here.
An good recent article on commercial math & visualization software is:
Braham, Robert. "Math & Visualization: new tools, new frontiers",
IEEE Spectrum 32, 11 (November 1995), p. 19-36.
The article contains tables comparing large number of commercial products.
There is no mention of the many excellent free products though.
* iii q520.1, "Comparative Reviews on Symbolic Algebra Packages"
* iii q520.2, "Web sites for Symbolic Algebra"
* iii q520.3, "References for Symbolic Algebra"
* iii q520.4, "Automatic Differentiation Tools"
Free Software for Symbolic Algebra:
* iii q520.5.1, "MuPAD"
* iii q520.5.2, "Jacal"
* iii q520.5.3, "GAP"
* iii q520.5.4, "PARI/GP"
* iii q520.5.5, "Form"
* iii q520.5.6, "GRTensorII"
* iii q520.5.7, "SAML"
* iii q520.5.8, "SACLIB"
* iii q520.5.9, "NTL - A Library for doing Number Theory"
* iii q520.5.10, "Yacas"
* iii q520.5.11, "Ginac"
===================================
q520.1. Comparative Reviews on Symbolic Algebra Packages
Michael Wester maintains a web page with his detailed review
of Axiom, Derive, Macsyma, Maple, Mathematica, Mupad, and Reduce,
as well as references and links to other reviews.
Wester's review compares the packages on 131 problems, mostly
from symbolic algebra.
http://math.unm.edu/~wester/cas_review.html Wester's www page
ftp://math.unm.edu/pub/wester/cas/Paper.ps Wester's paper via ftp
See the articles in Computers in Physics,
Vol 6 #4 and #5 [Jul/Aug, Sep/Oct, 1992].
Several sites devoted to "Comparison of Mathematica on Various Computers"
can be reached via:
http://smc.vnet.net/mathbench.html Christensen
There are some comparisons kept by Paulo Ney deSouza
on the Berkeley math gopher (in particular the file
Comparison, but also others):
gopher://math.berkeley.edu/11/Symbolic_Soft Berkeley Math gopher
See also the paper by Laurent Bernardin,
``A Review of Symbolic Solvers'', SIGSAM bulletin 31(1),
1996. Available in postscript form at
http://www.inf.ethz.ch/personal/bernardi/publications/review.ps Bernardin's review
Macsyma also has comparisons of Macsyma's commercial product vs. others at:
http://www.macsyma.com Macsyma
===================================
q520.2. Web sites for Symbolic Algebra
U.C. Berkeley
gopher://math.berkeley.edu U.C. Berkeley Math Dept. via gopher
ftp://math.berkeley.edu/pub U.C. Berkeley Math Dept. via ftp
A large site of courses, archives, pointers to other sites.
The Symbolic_Soft directory contains info on:
ALJABR, AMP, Articles_and_Books/, Available_Systems, Axiom
Bibliography, CALC, CLA, Calculus, Cayley, CoCoA, Comparison/
DELiA, DOE-Macsyma, Derive, FLAC, Form, GANITH, GAP, GNU-calc
GRTensorII, Galois, Gmp, JACAL, KAN, KANT, LIE, LiE, MALM, MAS, MPQS
Macaulay, Macsyma, Magma/, Maple/, Mathematica/, Maxima, Mercury
Mock-Mma, NCAlgebra, Numbers, On_Going/, PARI, PFSA, Paramacs
Reduce/, Reviews/, Ricci, SENAC/, SIMATH, STENSOR, Schoonschip
Schur, SymbMath, Theorist, UBASIC, Vaxima, Weyl, XPL, cas.tex
CAIN: The Computer Algebra Information Network
http://www.riaca.win.tue.nl/CAN/CAIN.html CAIN main site
http://www-math.uni-paderborn.de/personelles/user/cube/CAIN/ CAIN
CAIN contains information on symbolic algebra packages,
conferences, newsletters, bibliographies and tools.
It also contains pointers to a number of related information
servers.
As of December 1995, it contains info on the following:
* General purpose systems:
ALJABR, AXIOM, Derive, FORM, GNU-calc, MACSYMA Descendants, Macsyma,
Magma, Maple, Mathematica, MAXIMA, MuPAD, PARAMAX, PUNIMAX, REDUCE,
SENAC, Theorist, VAXIMA
* (Non)Commutative Algebra & Algebraic Geometry:
Albert, Bergman, CALI, CASA, CoCoA, FELIX, GANITH, GB, GRB,
GROEBNER (from RISC-Linz), GROEBNER (REDUCE package), IDEALS, KAN,
Macaulay, MAS, NCALGEBRA, SACLIB, Singular, WU
* Differential Equation Solvers & Tools:
List of Symmetry Programs (PostScript, gzip-compressed), CRACK, DELiA,
DESIR, Diffgrob2 (Manual: PostScript, gzip-formatted), DIMSYM, FIDE,
LIE (A.K. Head, in MuMath), Lie (Baumann, in Mathematica),
Lie-Baecklund Symmetries (Baumann, in Mathematica), liesymm, ODESOLVE,
PDELIE, SPDE, , StandardForm, SYM_DE, SYMMGRP.MAX (Manual: PostScript,
gzip-formatted)
* Finite Element Analysis:
MathFE, PDEase, SENAC/FEM (PostScipt, gzip-formatted); see also SENAC,
* Group Theory:
ANU Software, Cayley, CHEVIE, GAP, GRAPE, GUAVA, LiE,
LIE (REDUCE package), Magma, MeatAxe, Schur, Sisyphos, Symmetrica,
Weyl Groups and Hecke Algebras
* High Energy Physics:
FeynArts, FeynCalc, FORM, HEP, Schoonschip, Tracer
* Number Theory:
Galois, KANT, KASH, MALM, Numbers, PARI, SIMATH, UBASIC
* Tensor Calculus:
CARTAN, Classi, GRTensor, MathTensor, Redten, Ricci, SHEEP, STENSOR
* Experimental systems: PC Shareware with Symbolic Features:
AMP, Calculus and Differential Equations, CC4, CLA, Mathomatic,
PFSA, SymbMath, X(PLORE),
* Experimental Systems: Various Systems
AUTOMATA, QUOTPIC & TESTISOM, Computer Algebra Kit, FLAC, JACAL,
Mock-Mma, ORME, RepTiles, Asir, SimLab, Computer Tools for Analysis
and Simulation
SymbolicNet
http://symbolicnet.mcs.kent.edu/ SymbolicNet
Like CAIN, SymbolicNet contains information on symbolic algebra packages,
conferences, newsletters, bibliographies and tools.
As of October 1995, it contains info on the following packages:
Axiom, Derive, GANITH, GRTensor, Macsyma, Magma, Maple, Mathematica
MathSoft, MathTensor, Milo, MuPAD, Pari, Reduce, Schur, SymbMath
Number Theory Web
A large web site devoted to number theory resources.
http://www.math.uga.edu/~ntheory/web.html Number Theory Web
Things of Interest to Number Theorists
http://www.math.uga.edu/~ntheory/listi.html Number Theory
===================================
q520.3. References for Symbolic Algebra
Tan Kiat Shi and W.-H. Steeb, 1997
"SymbolicC++: An introduction to Computer Algebra
Using Object_Oriented Programming"
Springer-Verlag, 1997 ISBN 981-3083-55-7.
The complete source code in C++ is provided.
===================================
q520.4. Automatic Differentiation Tools
[Luiz Henrique de Figueiredo]:
A good starting point for automatic differentiation tools is:
http://www.mcs.anl.gov/autodiff Argonne National Lab
===================================
q520.5.1. MuPAD
http://www.mupad.de/ MuPAD
MuPAD has been strongly recommended by users. From the [author]:
MuPAD is a system for symbolic and numeric computation, parallel
mathematical programming and mathematical visualization. It is
intended to be a 'general purpose' computer algebra system.
MuPAD has easy-to-use language constructs for parallel
programming. A prerelease Version for parallel programming exists
for Sequent and Sun multiprocessor machines. Programming in
MuPAD's own programming language is supported by a comfortable
source code debugger. Window-based user interfaces for MuPAD exist
for the X-Window-System and the Apple Macintosh.
MuPAD is distributed for free (for non-commercial use).
It is not in the public domain; a registration is required.
===================================
q520.5.2. Jacal
ftp://prep.ai.mit.edu/pub/gnu/jacal Jacal
From the [author]:
JACAL is a symbolic mathematics system for the simplification and
manipulation of equations and single and multiple valued algebraic
expressions constructed of numbers, variables, radicals, and algebraic
functions, differential, and holonomic functions. In addition,
vectors and matrices of the above objects are included.
JACAL is written in Scheme. A version of Scheme (IEEE P1178 and R4RS
compliant) written in C is available with JACAL. SCM runs on Amiga,
Atari-ST, MacOS, MS-DOS, OS/2, NOS/VE, Unicos, VMS, Unix and similar
systems.
===================================
q520.5.3. GAP
ftp sites:
ftp://ftp.math.rwth-aachen.de/pub/gap/ GAP
ftp://archives.math.utk.edu/software/multi-platform/gap/ GAP
ftp://pell.anu.edu.au/pub/gap/ GAP
[author]:
GAP is a system for computational discrete algebra, which we have
developed with particular emphasis on computational group theory, but
which has already proved useful also in other areas. The name GAP is an
acronym for *Groups, Algorithms, and Programming*.
===================================
q520.5.4. PARI/GP
ftp://megrez.math.u-bordeaux.fr/pub/pari/ PARI/GP
Also at math.ucla.edu
[author]:
PARI/GP is a package which is aimed at efficient
computations in number theory, but also contains a large
number of functions unrelated to number theory. It is
somewhat related to a Computer Algebra System, but is
not really one since it treats symbolic expressions as
mathematical entities such as polynomials, series,
matrices, etc..., and not as expressions per se. However
it is often much faster than other CAS, and contains a
huge number of specific functions not found elsewhere,
essentially for use in number theory. In particular,
and especially so in the present release, there is a
very large package for working in general algebraic
number fields.
===================================
q520.5.5. Form
http://www.nikhef.nl/~form/ Form
[author]:
The symbolic manipulation program Form is a powerful tool to do large
algebraic calculations. It is an easy-to-learn language which is
complementary to large programs such as Maple and Mathematica in that
not much knowledge is built in, but Form provides you with the means
to grind quickly through large formulae. In this introductory course
the most-used commands are introduced and useful algorithms are
discussed. Many examples illustrate the text.
===================================
q520.5.6. GRTensorII
http://www.astro.queensu.ca/~grtensor/ GRTensorII via www
ftp://astro.queensu.ca/pub/grtensor GRTensorII via ftp
[author]:
GRTensorII is a computer algebra package for performing calculations
in the general area of differential geometry. Its purpose is the
calculation of tensor components on curved spacetimes specified in
terms of a metric or set of basis vectors. It is available in both
MapleV and Mathematica versions, and is distributed free of charge
===================================
q520.5.7. SAML
ftp://topo.math.u-psud.fr:/pub/bousch/saml-960828.tgz SAML
[author]:
SAML, the Simple Algebraic Math Library, is free.
Keep in mind that it's a work in progress. That's for Unix only.
===================================
q520.5.8. SACLIB
ftp://ftp.risc.uni-linz.ac.at/pub/saclib SACLIB
[Back in 1994, Andre Heck wrote]:
SACLIB is a library of C programs for computer algebra
derived from the SAC2 system. Hoon Hong was the
main instigator. Sometime early in 1990 he proposed to
translate SAC2 (which was written in the ALDES
language) into C instead of Fortran (as it had been since
1976), and he quickly wrote the required translator. The
results were rewarding in several ways. Hoon Hong, George E.
Collins and Jeremy Johnson, working together at
Ohio State University, observed a speedup by a factor of
about two in most applications and the powerful
debugging facilities associated with C became available.
Later that year Hoon finished his doctorate and moved to
RISC, where Bruno Buchberger was writing a book on
Groebner bases and working on a set of programs to go with
it. He found that SAC2 was the only computer
algebra system in which he could write these programs
without an unacceptable sacrifice in computational
efficiency. It became apparent that for similar reasons
other researchers would benefit greatly from the
availability of a library of C programs derived from SAC2.
Subsequently Bruno did much to promote and
facilitate the preparation of the library for distribution.
Although the translated programs were correct, they needed
to be reformatted for user consumption, a users
guide was required, and the developers had compulsions to
make some minor improvements. Jeremy Johnson
made many recent improvements to the algebraic number
algorithms and wrote the corresponding chapter of
the User Guide, among other things. Werner Krandick made
improvements to the polynomial real root
algorithms and wrote the corresponding chapter in the User
Guide. Mark Encarnacion wrote three chapters of
the User Guide and also converted the polynomial input and
output algorithms to modern notation from the
original "Fortran notation". Ana Mandache, Andreas Neubacher
and Hoon Hong all toiled long hours editing
and reformatting programs. Andreas deserves special
recognition. He initiated the writing of the manual, wrote
three chapters of the manual and two of the appendices, and
did all the required system maintenance. To
facilitate experimenting with the functions in the library,
Herbert Vielhaber implemented isac, the interactive
shell for SACLIB. He also wrote the corresponding appendix
of the manual.
This initial version of SACLIB is just the beginning of what
is to come. The developers know how to improve
several of the programs in the current system and will do it
for subsequent versions. Some basic functionalities
are largely undeveloped in the currrent system (e.g. linear
algebra) but they will be supplied in subsequent
versions. Some more advanced functionalities (e.g.
polynomial complex roots and quantifier elimination) are
nearly ready and will be forthcoming soon. Also it is
expected that users of the system will write programs based
on the ones we distribute and offer them to other users.
===================================
q520.5.9. NTL - A Library for doing Number Theory
http://www.shoup.net/ NTL
[author]:
* NTL is a high-performance, portable C++ library providing data structures
and algorithms for manipulating signed, arbitrary length integers, and for
vectors, matrices, and polynomials over the integers and over finite fields.
* NTL uses state-of-the-art algorithms. In particular, its code for
polynomial arithmetic is one of the fastest available. Early versions of NTL
have been used to set "world records" for polynomial factorization and point
counting on elliptic curves.
* NTL is written entirely in C++, and can be easily installed on just about
any Unix platform, including PCs, and 32- and 64-bit workstations. Despite
the fact that NTL is written in C++ and avoids assembly, NTL's performance
is generally much better than is typical of such portable libraries.
* NTL is relatively easy to use, and it provides a good environment for easily
and quickly implementing new number-theoretic algorithms, without
sacrificing performance.
* NTL is free software that is intended for research and educational purposes
only.
===================================
q520.5.10. Yacas: Yet another computer algebra system
http://www.xs4all.nl/~apinkus/yacas.html Yacas
[author]:
Yacas (Yet Another Computer Algebra System) is an open source
general purpose computer algebra
system with a pleasant syntax.
Yacas is written in very clean c++ code, and is very portable.
It can compile stand-alone, and is easily
embeddable. Yacas contains a native arbitrary precision
arithmetic module, but can also be used with GMP.
Things implemented include: arbitrary precision, rational numeric,
vector, complex, and matrix
computations (including inverses and determinants and solving
matrix equations), derivatives, solving,
Taylor series, numerical solving (Newtons method), and a lot more
non-mathematical algorithms. The
language natively supports variables and user-defined functions.
There is basic support for univariate
polynomials, integrating functions and tensor calculations.
===================================
q520.5.11. Ginac
http://www.ginac.de/ Ginac
The GiNaC open framework for symbolic computation within the C++ programming language does not try to define a language of its own as conventional CAS do. Instead, it extends the capabilities of C++ by symbolic manipulations.
===========================================================================
q530. Cryptography (Cryptology)
See newsgroups sci.crypt, sci.crypt.research.
There are numerous cryptography FAQs. See:
ftp://rtfm.mit.edu/Index-byname MIT's rtfm FAQ index
===========================================================================
q540. Fractals
Although generating fractals usually involves floating
point numbers, fractals are generally not considered part of NA.
The FAQ is at:
ftp://rtfm.mit.edu/pub/usenet-by-group/news.answers/fractal-faq MIT's rtfm
newsgroups: sci.fractals
===========================================================================
q550. Neural Networks
Although neural nets use optimization techniques,
they are generally regarded as a separate field.
See:
ftp://ftp.sas.com/pub/neural/FAQ.html Warren Sarle's FAQ
ftp://rtfm.mit.edu/pub/usenet-by-group/comp.answers/ai-faq/neural-nets Warren Sarle's FAQ
newsgroups: comp.ai.neural-nets
===========================================================================
q560. Discrete algorithms
A good intro text for discrete algorithms is:
Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest.
Introduction to Algorithms
MIT Press, 1990.
ISBN 0-262-03141-8
Telephone: 617-253-5641, 800-356-0343
See also the newsgroup comp.theory.
See: Center for Discrete Mathematics and Theoretical Computer Science
(DIMACS) at:
http://dimacs.rutgers.edu/ DIMACS
Discrete algorithms include:
* Sorting algorithms
* Network traversal (traveling salesman, etc)
* Primality testing (see the cryptography FAQs mentioned above).
* Automata Theory
* Many other fields
===========================================================================
q570. Constraints
newsgroup: comp.constraints
ftp://rtfm.mit.edu/pub/usenet-by-group/comp.answers/constraints-faq FAQ
University of New Hampshire Constraint Computation Center
Configuration involves selecting and arranging parts to fit
problem constraints. Configuration problems may involve design,
manufacturing, sales, installation and maintenance. The parts need not
be physical, e.g. they may be actions in plans.
http://www.cs.unh.edu/ccc/config/ U. of New Hampshire
Constraints archive, containing publications, benchmarks,
biblio, faq, ftp sites & www pages:
http://www.cs.unh.edu/ccc/archive/ Constraints Archive
===========================================================================
q580. Genetic Algorithms
For a light-hearted FAQ and overview, see the
Hitch-Hiker's Guide to Evolutionary Computation
http://surf.de.uu.net/encore/www/ Hitch-Hiker's Guide via www
PGAPack, Parallel Genetic Algorithm Library, by David Levine
[David Levine]
PGAPack is a general-purpose, data-structure-neutral, parallel genetic
algorithm library. It is intended to provide most capabilities desired in a
genetic algorithm library, in an integrated, seamless, and portable manner.
Key features include:
* Callable from Fortran or C.
* Runs on uniprocessors, parallel computers, and workstation networks.
* Binary-, integer-, real-, and character-valued native data types.
* Full extensibility to support custom operators and new data types.
* Easy-to-use interface for novice and application users.
* Multiple levels of access for expert users.
* Parameterized population replacement.
* Multiple crossover, mutation, and selection operators
* Easy integration of hill-climbing heuristics.
* Extensive debugging facilities.
* Large set of example problems.
* Detailed users guide
PGAPack is available from:
http://www.mcs.anl.gov/pgapack.html PGAPack
ftp://ftp.mcs.anl.gov/pub/pgapack/pgapack.tar.Z PGAPack via ftp
David Levine can be reached at:
levine@mcs.anl.gov
MCS 221 C-216 Argonne National Laboratory Argonne, Illinois 60439
(708)-252-6735 Fax: (708)-252-5986
===========================================================================
q590. Simulated Annealing
Adaptive Simulated Annealing Package (ASA), by Lester Ingber
http://www.alumni.caltech.edu/~ingber/ ASA
An optimization algorithm for nonlinear and stochastic systems.
Also, Skip Carter's home page has info and software on simulated annealing,
as well as other topics: digital filters, Kalman filters, neural nets,
and C++ software.
http://www.taygeta.com/annealing/simanneal.html Skip Carter's page
===========================================================================
q800. Teaching and Academic Software
* iii q805, "Ted Brown's Work on Physics and Engineering"
* iii q810, "Gleb Beliakov's Work on Numerical Analysis"
* iii q815, "Julian Noble's Computational Methods of Physics course"
q805. Ted Brown's Work on Physics and Engineering
Ted Brown has written a set of tutorials on vectors,
dynamics, electricity and magnetism. They are implemented
for the PC DOS environment, but he might be convinced
to write a more general version.
email: tbrown@tekotago.ac.nz
[Ted Brown]:
The tutorial, on VECTORS, is an interactive program suitable for
first year students, in that it presumes no previous knowledge of the
area.
The principal sections are on Addition and Difference of vectors by
graphical construction, and by components.
All the construction is done on the screen, with magnitudes and
angles being presented dynamically in a box, as the mouse is moved
about. Magnitudes and directions of resultants are read directly from
the screen.
Students are required to logon, and records are kept of who has been
using the program, for how long, and what their current score is.
This information is only available through an instructor module.
The program runs in Windows, resolution 640*480, 256 colours, on a
standalone machine, or on a network, and its size is around 5 or 6
Meg.
If anyone is interested in getting more details, I can be contacted
on "tbrown@tekotago.ac.nz"
I have, over the last few years written a number of physics
tutorials, in the general areas of dynamics, electricity and
magnetism, but they have all been written for DOS. If I thought there
was some interest, I would re-write them for Windows.
Ted.
===================================
q810. Gleb Beliakov's Work on Numerical Analysis
PNA is designed for the Maple V (release 2 or 3) environment.
"Practicum in Numerical Analysis (PNA)" is a set of laboratory tasks
designed to be a supplement to the course of numerical analysis. The
exercises illustrate the basic numerical methods, show their
advantages and limitations and help to understand the behavior of
numerical solutions. The interactive use of a computer permits one to
understand the properties of the algorithms to an extent impossible to
achieve reading textbooks. First, it is possible to present more
realistic examples of the usage of numerical methods (bigger systems
of equations, more iterations), and second, the students can freely
change given illustrations in order to try them out and to clarify the
behavior of the solutions. Finally, the discussed algorithms can be
used by the students in their further studies by either linking them
to bigger programs as a library or by copying the text into another
programming environment with slight changes in the syntax.
It should be noted that PNA is not a substitute for a textbook but a
complement to classical educational tools.
===================================
q815. Julian Noble's Computational Methods of Physics course homepage
http://Landau1.phys.virginia.edu/classes/551/ Computational Methods
There are programs, lecture notes and programs to be found there.
===========================================================================