Ocaml in String Theory

[Thomas Fischbacher <Thomas.Fischbacher@Physik.Uni-Muenchen.DE>]

Ladies and Gentlemen,

a happy new year to all readers of this list.

For a non-mainstream language like Ocaml, it is evidently of great 
importance to have good answers to the question about its practical 
relevance. It seems as if we now have another nice application to add to 
the list: in today's official arxiv.org listing, the following 
preprint paper (by myself and two colleagues from the Albert Einstein 
Institute) appeared:

 http://www.arxiv.org/abs/hep-th/0412331

Physically speaking, one of the hot topics in string theory today is the 
conjectured equivalence of certain quantum field theories which neither at 
the classical level nor as quantum theories have an intrinsic length scale
on the one side - so-called conformal field theories - and string theory 
on a space-time which approaches constant negative curvature at infinity 
(i.e. anti deSitter space) - see e.g.
http://www.phys.lsu.edu/mog/mog18/node10.html

What we did was to provide further strong evidence that the physical key 
property of integrability holds, however another important property known 
as BMN scaling (sorry, I cannot go into details) is violated in 
quite non-obvious ways.

Computationally, what we had to do in order to achieve this result was to 
develop a fast algorithm which furthermore can be implemented close to the 
machine level that allows us to sum literally billions of contributions 
from different planar feynman graphs with four loops in them. Planarity is 
the key property here that makes this calculation feasible - if we 
included the non-planar graphs as well, we would have had to deal with an 
estimated number of contributions of about half a quadrillion.

At the much simpler three loop level, our approach is faster than 
previous ones (using the FORM program which was built explicitly for fast 
quantum field theoretic calculations) by about a factor of 100. This comes 
in part from our improved algorithm that singles out planar graphs (and 
hence scales much better than algorithms which do not), in part from 
doing term transformations not in an interpreted fashion, but 
directly at machine code level (via compiled ocaml), furthermore from 
carefully ensuring not to do unnecessary work when simplifying terms,
from evil hacks (such as abusing the FPU to do exact(!) fraction 
arithmetics for fractions of the form <small numerator>/<small power of 2>),
and - quite important - from certain algorithmic tricks from the 
functional programmer's toolbox such as continuation coding and lazy 
evaluation. In other words, it would not at all have been possible
in anything else but a fast compiled functional language. Nevertheless, 
we still had to burn 88 000+ CPU-hours on 2 GHz Athlon (and Opteron) 
hardware to do the largest piece of the calculation and we are very 
grateful towards our numerical colleagues for providing us with 
appropriate resources - this is true symbolic supercomputing.

While we (the authors) are not yet sure about this, we think to have 
strong reason to believe that this may be the (presumably by orders of 
magnitude) largest symbolic algebra calculation performed so far - 
counting the number of term transformations. (Excluding cypher breaking 
and prime search attempts, as the underlying questions hardly can be 
regarded as of symbolic nature.) We know that there have been quite large 
four-loop QCD calculations before involving something like 50 000 
individual graphs that furthermore had to deal with some transformations 
on integrals (which we do not have, due to a certain kind of reduction we 
perform in our model) and hence are somewhat more difficult to calculate 
than our graphs - but certainly not by a factor of 100 000. If anyone 
knows better and can tell us about an even larger symbolic calculation, we 
would be glad to hear about it.

While our paper is essentially for physicists, it features a 
self-contained appendix explaining the algorithmic and implementation
aspects of our work that should be readable especially for people with a 
computer science background. Furthermore, one can download (details in the 
paper) our source. Unfortunately, in order to actually build the program, 
one needs a somewhat large development environment, as some of the ocaml 
source and data files are machine generated by perl and CMU Common Lisp. 
Admittedly, the code could be cleaner, but one should keep in mind here 
a few external factors (i.e. pressure to publish new physical 
results) which are different for computer scientists and physicists. 
Well, it's not as bad as quite a lot of code in physics, and I 
think I can show it around without having to pull a brown paper bag over 
my head, but the style is certainly not one I'd like to see in textbooks.
Given the time (which I at present do not have), I'd like to clean it up 
a bit more. 

-- 
regards,               tf@cip.physik.uni-muenchen.de              (o_
 Thomas Fischbacher -  http://www.cip.physik.uni-muenchen.de/~tf  //\
(lambda (n) ((lambda (p q r) (p p q r)) (lambda (g x y)           V_/_
(if (= x 0) y (g g (- x 1) (* x y)))) n 1))                  (Debian GNU)