Difference between revisions of "Applications and libraries/Mathematics"

Revision as of 11:37, 9 August 2008

Applications

Physics

Meep: Meep (or MEEP) is a free finite-difference time-domain (FDTD) simulation software package developed at MIT to model electromagnetic systems.

Numeric Quest: Jan Skibinski's Numeric Quest library provides modules that are useful for Quantum Mechanics, among other things.

Libraries

Linear algebra

GSLHaskell: High level functional interface to standard linear algebra computations and other numerical algorithms based on the GNU Scientific Library and LAPACK. Includes numerical differentiation, integration, Fourier transforms, polynomial root-finding, and support for gnuplot. MacOS X.

Wrapper to CLAPACK

Digital Signal Processing: Modules for matrix manipulation, Fourier transform, interpolation, spectral estimation, and frequency estimation.

Index-aware linear algebra: Frederik Eaton's library for statically checked matrix manipulation in Haskell

Numeric Quest: Jan Skibinski's Numeric Quest library provides several modules that are useful for linear algebra in general, among other things.

vector-space: The vector-space package defines classes and generic operations for vector spaces and affine spaces. It also defines a type of infinite towers of generalized derivatives (linear transformations).

CalDims: This is not simply a library providing a new type of Num class, but stand-alone calculation tool that supports user defined functions and units (basic and derrived), so it can provide dimension-save calculation (not embedded but via shell). Calculations can be modified/saved via shell. It uses rational numbers to avoid rounding errors where possible.

Dimensional: Library providing data types for performing arithmetic with physical quantities and units. Information about the physical dimensions of the quantities/units is embedded in their types and the validity of operations is verified by the type checker at compile time. The boxing and unboxing of numerical values as quantities is done by multiplication and division of units.

Number representations

Decimal numbers

Decimal arithmetic library: An implementation of real decimal arithmetic, for cases where the binary floating point is not acceptable (for example, money).

Real and rational numbers

There are several levels of handling real numbers and according libraries.

Arbitrary precision

Numbers have fixed precision
Rounding errors accumulate
Sharing is easy, i.e. in sqrt pi + sin pi, pi is computed only once
Fast, because the routines can make use of the fast implementation of Integer operations

Numeric Quest: Jan Skibinski's Numeric Quest library provides, among other things, a type for arbitrary precision rational numbers with transcendental functions.

FixedPoint.hs: part of NumericPrelude project

AERN-Real: contains arbitrary precision interval arithmetic for approximating exact real numbers in a style similar to Mueller's iRRAM and Lambov's RealLib

AERN-RnToRm: contains arithmetic of piecewise polynomial function enclosures that efficiently approximate multi-dimensional real functions to arbitrary precision

Dynamic precision

You tell the precision, an expression shall be computed to and the computer finds out, how precise to compute the input values.
Rounding errors do not accumulate
Sharing of temporary results is difficult, that is in sqrt pi + sin pi, pi will certainly be computed twice, each time with the required precision.
Almost as fast as arbitrary precision computation

ERA is an implementation (in Haskell 1.2) by David Lester.: It is quite fast, possibly the fastest Haskell implementation. At 220 lines it is also the shortest. Probably the shortest implementation of exact real arithmetic in any language.; The provided number type CReal is instance of the Haskell 98 numeric type classes and thus can be used whereever you used Float or Double before and encountered some numerical difficulties.; Here is a mirror: http://darcs.augustsson.net/Darcs/CReal/

IC-Reals is an implementation by Abbas Edalat, Marko Krznarć and Peter J. Potts.: This implementation uses linear fractional transformations.

Few Digits by Russell O'Connor.: This is a prototype of the implementation he intendeds to write in Coq. Once the Coq implementation is complete, the Haskell code could be extracted producing an implementation that would be proved correct.

COMP is an implementation by Yann Kieffer.: The work is in beta and relies on new primitive operations on Integers which will be implemented in GHC. The library isn't available yet.

Dynamic precision by lazy evaluation

The real numbers are represented by an infinite datastructure, which allows you to increase precision successively by evaluating the data structure successively. All of the implementations below use some kind of digit stream as number representation. Sharing of results is simple. The implementations are either fast on simple expressions, because they use large blocks/bases, or they are fast on complex expressions, because they consume as little as possible input digits in order to emit the required output digits.

BigFloat is an implementation by Martin Guy.: It works with streams of decimal digits (strictly in the range from 0 to 9) and a separate sign. The produced digits are always correct. Output is postponed until the code is certain what the next digit is. This sometimes means that no more data is output.

In "The Most Unreliable Technique in the World to compute pi" Jerzy Karczmarczuk develops some functions for computing pi lazily.

NumericPrelude: positional numbers

Represents a real number as pair (exponent,[digit]), where the digits are Ints in the open range (-basis,basis). There is no need for an extra sign item in the number data structure. The basis can range from 10 to 1000. (Binary representations can be derived from the hexadecimal representation.) Showing the numbers in traditional format (non-negative digits) fails for fractions ending with a run of zeros. However the internal representation with negative digits can always be shown and is probably more useful for further processing. An interface for the numeric type hierarchy of the NumericPrelude project is provided.

It features

basis conversion
basic arithmetic: addition, subtraction, multiplication, division
algebraic arithmetic: square root, other roots (no general polynomial roots)
transcendental arithmetic: pi, exponential, logarithm, trigonometric and inverse trigonometric functions

Type class hierarchies

There are several approaches to improve the numeric type class hierarchy.

Dylan Thurston and Henning Thielemann's Numeric Prelude: Experimental revised framework for numeric type classes. Needs hiding of Prelude, overriding hidden functions like fromInteger and multi-parameter type classes. Probably restricted to GHC.

Jerzy Karczmarczuk's approach

Serge D. Mechveliani's Basic Algebra proposal

Andrew Frank's approach: The proposal: ftp://ftp.geoinfo.tuwien.ac.at/frank/numbersPrelude_v1.pdf

Haskell Prime: Ongoing efforts for the language revision

Discrete mathematics

Number Theory Library: Andrew Bromage's Haskell number theory library, providing operations on primes, fibonacci sequences and combinatorics.

HGAL: An haskell implementation of Brendan McKay's algorithm for graph canonic labeling and automorphism group. (aka Nauty)

Computational Oriented Matroids: is a book by Jürgen G. Bokowski, where he develops Haskell code for Matroid computations.

Computer Algebra

DoCon - Algebraic Domain Constructor: A library for Algebra, turns GHCi into a kind of Computer Algebra System

Papers by Jerzy Karczmarczuk: Some interesting uses of Haskell in mathematics, including functional differentiation, power series, continued fractions.

Statistics

hstats: Statistical Computing with Haskell

Miscellaneous libraries

HaskellMath: The HaskellMath library is a sandbox for experimenting with mathematics algorithms. So far I've implemented a few quantitative finance models (Black Scholes, Binomial Trees, etc) and basic linear algebra functions. Next I might work on either computer algebra or linear programming. All comments welcome!

Haskell for Maths: David Amos' collection of math libraries in Haskell - including number theory, commutative algebra, combinatorics, permutation groups and more.

Various math stuff by Henning Thielemann: This is some unsorted mathematical stuff including: GNUPlot wrapper, portable grey map (PGM) image reader and writer, simplest numerical integration, differentiation, zero finding, interpolation, solution of differential equations, combinatorics, some solutions of math riddles, computation of fractal dimensions of iterated function systems (IFS)

Numeric Quest: Jan Skibinski wrote a collection of Haskell modules that are useful for Mathematics in general, and Quantum Mechanics in particular.

Some of the modules are hosted on haskell.org. They include modules for:

Rational numbers with transcendental functions
Roots of polynomials
Eigensystems
Tensors
Dirac quantum mechanics

Other modules in Numeric Quest are currently only available via the Internet Archive. They include, among many other things:

See the Numeric Quest page for more information.

Geometric Algorithms: A small Haskell library, containing algorithms for two-dimensional convex hulls, triangulations of polygons, Voronoi-diagrams and Delaunay-triangulations, the QEDS data structure, kd-trees and range-trees.

Adaptive Simulated Annealing: A Haskell interface to Lester Ingber's adaptive simulating annealing code.

Hmm: Haskell Metamath: Hmm is a small Haskell library to parse and verify Metamath databases.

Probabilistic Functional Programming: The PFP library is a collection of modules for Haskell that facilitates probabilistic functional programming, that is, programming with stochastic values. The probabilistic functional programming approach is based on a data type for representing distributions. A distribution represent the outcome of a probabilistic event as a collection of all possible values, tagged with their likelihood. A nice aspect of this system is that simulations can be specified independently from their method of execution. That is, we can either fully simulate or randomize any simulation without altering the code which defines it.; Get Darcs repository: darcs get http://darcs.haskell.org/probability/

Sinc function

Gamma and Beta function

Boolean: A general boolean algebra class and some instances for Haskell.

HODE: HODE is a binding to the Open Dynamics Engine. ODE is an open source, high performance library for simulating rigid body dynamics.

Ranged Sets: A ranged set is a list of non-overlapping ranges. The ranges have upper and lower boundaries, and a boundary divides the base type into values above and below. No value can ever sit on a boundary. So you can have the set $(2.0,3.0]\cup (5.3,6)$ .

hhydra: Hhydra is a tool to compute Goodstein successions and hydra puzzles described by Bernard Hodgson in his article 'Herculean or Sisyphean tasks?' published in No 51 March 2004 of the Newsletter of the European Mathematical Society.

This page contains a list of libraries and tools in a certain category. For a comprehensive list of such pages, see Applications and libraries.

@@ Line 76: / Line 76: @@
 ;[http://cvs.haskell.org/darcs/numericprelude/src/Number/FixedPoint.hs FixedPoint.hs]
 :part of NumericPrelude project
+;[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/AERN-Real AERN-Real]
+:contains arbitrary precision ''interval arithmetic'' for approximating exact real numbers in a style similar to Mueller's iRRAM and Lambov's RealLib
+;[http://hackage.haskell.org/cgi-bin/hackage-scripts/package/AERN-Real AERN-RnToRm]
+:contains arithmetic of ''piecewise polynomial function enclosures'' that efficiently approximate multi-dimensional real functions to arbitrary precision
 ===== Dynamic precision =====