From 1992-1994 Henry Cejtin and I were funded by the NSF under the
auspices of the Geometry Center to develop a pilot object system for
geometric computation. This was based on the Scheme programming language.
You can read our final report. You can also
check out some of the code
You can find some more recent miscellaneous Scheme code here. This contains some functional utilities, some mathematical code (including code to
find zeros of monotone functions by bisection, random and otherwise
permutations and subsets, matrix and vector utilities, and so on), statistical code (including code to
compute the error function and the cumulative distribution function of
bivariate normal), code to compute
simple option pricing models (including the Black-Scholes model
and some more sophisticated models taking account of dividents),
number theoretic code (which
computes the extended gcd, and finds primes using the sieve of
Eratosthenes, and implements the Chinese Remainder Theorem), and some
code to compute determinants of
floating point, modular, and integer matrices. The integer case is
done using a Chinese Remainder trick, for greater efficiency.
There is also a fairly complete implementation of the mergesort algorithm.
Finally there are some simple
examples.
The Python program gengraph.py uses the elegant algorithm due to
Nick Wormald to generate random
k-regular graphs (the algorithm is not really useable for k > 6). The
code in eigentest.py uses the interface to
linear algebra routines provide by
Numerical Python to
compute eigenvalues of the resulting graphs. This is a port of
1995-1996 code of mine which was the basis of the paper of D.Jakobson,
S.Miller, Z. Rudnick and myself on quantum chaos in graphs.
C versions of much of this are also availble. One example is
genbipartite.c which generates bipartite
graphs. Another is dogirth.c which computes
the girth of graphs.
Update: (March 6, 2005): you can now also compute the connected
components of a graph, see ccomps.py.
But wait, there is more (also March 6, 2006): if you have a simplicial
complex of dimension n, where each top-dimensional simplex is given by
the list of its vertices, you can compute the graph whose vertices are
the top-dimensional faces, and the edges correspond to two
top-dimensional faces sharing an n-1 dimensional face, check out
tetra.py
More still (March 18): you will need some
utilities, but with these in hand, you can compute invariants of point sets in Euclidean
spaces, to wit, given k points in R^n, you can compute the
inradius and the circumradius of the k-1 dimensional simplex they
span, as well as the volume and the surface area and the gram matrix
of the simplex. Truly, happy days are here again!
March 27: There is now also a C implementation of the graph connected components analyser. (March
28: added a couple of lines which adds the ability to compute
distances from a given root vertex). There is
also a wrapper of
gengraph.py which makes the output be the same as the input of
the connected components program.
If you want to be able to select a number of M random lines from an N
line file (useful in statistical applications for bootstrapping, etc)
you can use these little utilities, which use
awk and the shell.
Some of my work in crystallography (with Mike Treacy) has led me to implement both a conjugate gradient, and a tree
annealing algorithms.
If you have ever needed to generate a list of legal dates, you will
have use for the following (very slow but
entertaining) unix utility. After un-tarring it, for example,
daterange 20040101 20040331 will give a list of legal dates in the
first three months of 2004.
When I am not programming in C or python, I favor Scheme and ML.
More programs in these and other languages, living and dead, will appear
here shortly, so watch this space. Work related to computational
finance will eventually appear at the Rivin Financial site.