Nested loop limit?

[Fernando Perez]

Dan Christensen wrote:

> Well, in a computation in quantum gravity, I have the C code shown
> below.  It has exactly 20 nested for loops!  There are of course
> other ways to write it, but given the number of iterations, speed
> is the bottom line.  Unfortunately, this is only the simplest test
> case of a larger problem...

You might want to have a look at:

http://amath.colorado.edu/pub/wavelets/papers/pnas.ps.gz

The approach outlined here is a fairly generic framework to tackle
high-dimensionality problems, there's another preprint with more examples
coming down the pipeline.

With d=20, since your complexity for truly nested stuff goes like N^d you are
hosed for almost any value of N.  Combining the ideas from the paper above
with:

http://amath.colorado.edu/pub/wavelets/papers/car.ps.gz

it is possible to write separated forms of many interesting kernels in
mathematical physics, providing algorithms which scale linearly with d (albeit
with big constants in front).

I'd like to know in a bit more detail what the context of your calculation is,
and whether the 20 comes from looping over dimesionalities of some
string-derived model or something else.  We're very interested in finding
contexts where these dimesionality-reduction approaches may be used.  While my
background is not in quantum gravity, if you keep the discussion generic enough
I should be able to follow (keep it bounded by general relativity, the standard
model and introductory stringy stuff and I should be fine).

Feel free to contact me directly at fperez AT colorado DOT edu if you don't feel
like talking about quantum gravity on c.l.py :)

Regards,


f