Integral interval exchange transformation

[videlec]

An iet with integral lengths is completely periodic. It is then interesting to know

• how many periodic components there are
• what shapes do they have (width and height)

It would be nice to be able to do this with intervalxt and compare timings with the code in surface_dynamics.interval_exchanges.integer_iet. In the end we might get rid of this part of surface_dynamics.

A typical run that run through all integral vectors with sum 50 for the permutation 0123456 / 6543210

import surface_dynamics.interval_exchanges.integer_iet as ii
sage: %time ii.interval_exchange_statistics([0,1,2,3,4,5,6], [6,5,4,3,2,1,0], 50)
CPU times: user 25.1 s, sys: 17 ms, total: 25.1 s
Wall time: 25.2 s
{3: 5996550, 4: 332178, 2: 6934796, 1: 720292}

[saraedum]

Just running DynamicalDecomposition::decompose on each of these IETs takes much more than 25s with intervalxt. (I can do the ones summing to 25 in that time which is only a very small number.)

Of course there's a lot of stuff being done in intervalxt that does not matter for this application.

[saraedum]

With a bunch of easy changes, I got a factor of 10 in performance in this case. I get to the ones summing to 35 with this in 25s.

Another factor of 10 seems to be necessary to get to the performance of surface dynamics. Looking at the profiler, a factor 50 might be doable actually.

Currently, 40% of the time is spent in malloc/free, i.e., using a memory pool should get rid of most of this and 10% of the time is spent in Boshernitzan related logic. Still, we're far from 50 with these changes and there's a lot of other things that could (and should) be optimized. Then again, most of this is negligible when not using integers since arithmetic quickly becomes dominating then.

[videlec]

Nice!

Indeed there are O(1) allocations in surface_dynamics (ie independent of the sum) as I am reusing a single interval exchange data structure. Though, I am also not computing the complete statistics: I completely ignore how the cylinders are glued together and simply record their numbers and sizes.

Why is Boshernitzan logic taking time here? SAF is zero and Boshernitzan should be ignored because useless.

Also in surface_dynamics I am using native integers and not GMP. Which length data type did you use?

It would be interesting to benchmark another similar situations related to non-arithmetic Veech surfaces (see #121). I believe that in this situation, the arithmetic is not too costly as applying the Zorich induction decreases the bitsize (if appropriately normalized... which is something that we do not do).

[saraedum]

Why is Boshernitzan logic taking time here? SAF is zero and Boshernitzan should be ignored because useless.

Absolutely, but there's no optimization for that in the code yet.

Which length data type did you use?

Mostly int but some bits use mpz which means costly allocations.

[saraedum]

I completely ignore how the cylinders are glued together and simply record their numbers and sizes.

Ok. That's unfair competition then ;) If I ignore that, I can do it in 33s on my laptop. Still 25% are in malloc so I guess the two approaches are (unsurprisingly) similarly fast.

[videlec]

I completely ignore how the cylinders are glued together and simply record their numbers and sizes.

Ok. That's unfair competition then ;) If I ignore that, I can do it in 33s on my laptop. Still 25% are in malloc so I guess the two approaches are (unsurprisingly) similarly fast.

I am precisely interested in how cylinders are glued together :) I was not able to get these statistics with surface_dynamics.