From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Delivered-To: caml-list@yquem.inria.fr Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by yquem.inria.fr (Postfix) with ESMTP id 70F61BB81 for ; Mon, 3 Jan 2005 13:13:17 +0100 (CET) Received: from pauillac.inria.fr (pauillac.inria.fr [128.93.11.35]) by concorde.inria.fr (8.13.0/8.13.0) with ESMTP id j03CDHI2000708 for ; Mon, 3 Jan 2005 13:13:17 +0100 Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id NAA32505 for ; Mon, 3 Jan 2005 13:13:16 +0100 (MET) Received: from mail.physik.uni-muenchen.de (mail.physik.uni-muenchen.de [192.54.42.129]) by nez-perce.inria.fr (8.13.0/8.13.0) with ESMTP id j03CDGmJ012728 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=FAIL) for ; Mon, 3 Jan 2005 13:13:16 +0100 Received: from localhost (unknown [127.0.0.1]) by mail.physik.uni-muenchen.de (Postfix) with ESMTP id EA10120028 for ; Mon, 3 Jan 2005 13:13:15 +0100 (CET) Received: from mail.physik.uni-muenchen.de ([127.0.0.1]) by localhost (mail.physik.uni-muenchen.de [127.0.0.1]) (amavisd-new, port 10024) with LMTP id 25042-01-13 for ; Mon, 3 Jan 2005 13:13:12 +0100 (CET) Received: from mailhost.cip.physik.uni-muenchen.de (kaiser.cip.physik.uni-muenchen.de [141.84.136.1]) by mail.physik.uni-muenchen.de (Postfix) with ESMTP id A81DF20027 for ; Mon, 3 Jan 2005 13:13:12 +0100 (CET) Received: from eiger.cip.physik.uni-muenchen.de (eiger.cip.physik.uni-muenchen.de [141.84.136.54]) by mailhost.cip.physik.uni-muenchen.de (Postfix) with ESMTP id 9B36426E89 for ; Mon, 3 Jan 2005 13:13:12 +0100 (CET) Received: by eiger.cip.physik.uni-muenchen.de (Postfix, from userid 3092) id 8CEED3CBC; Mon, 3 Jan 2005 13:13:12 +0100 (CET) Received: from localhost (localhost [127.0.0.1]) by eiger.cip.physik.uni-muenchen.de (Postfix) with ESMTP id 8A7D92D713 for ; Mon, 3 Jan 2005 13:13:12 +0100 (CET) Date: Mon, 3 Jan 2005 13:13:12 +0100 (CET) From: Thomas Fischbacher To: caml-list@inria.fr Subject: Ocaml in String Theory Message-ID: X-BOFH: Daemons did it MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Virus-Scanned: amavisd-new at physik.uni-muenchen.de X-Miltered: at concorde with ID 41D936DD.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Miltered: at nez-perce with ID 41D936DC.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Spam: no; 0.00; ocaml:01 ocaml:01 evidently:01 non-obvious:01 programmer's:01 lazy:01 symbolic:01 symbolic:01 algebra:01 model:01 admittedly:01 einstein:98 10.:98 cip:98 cip:98 X-Spam-Checker-Version: SpamAssassin 3.0.0 (2004-09-13) on yquem.inria.fr X-Spam-Status: No, score=0.0 required=5.0 tests=none autolearn=disabled version=3.0.0 X-Spam-Level: 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 /), 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)