intervalxt

Interval Exchange Transformations

intervalxt is a C++/Python library which implements algorithms on Interval Exchange Transformations (IETs).

In particular, we implement the Boshernitzan Algorithm and Rauzy Induction on IETs. Our principal application is the decomposition of a measured foliation into periodic and minimal components. We certify that a component is minimal with the Boshernitzan Algorithm or by certifying that the Rauzy Induction will be looping infinitely. Note that presently the algorithm is probably incomplete; in rare cases no further decomposition of a component seems to be possible, nevertheless, our criteria fail to certify minimality of the component.

Source tarballs can be downloaded at https://github.com/flatsurf/intervalxt/releases.

This repository contains two related projects:

• libintervalxt a C++ library
• pyintervalxt a Python wrapper for libintervalxt

Build and Develop intervalxt with pixi

If you have cloned the source repository, make sure to pull in all the third-party header-only libraries by running:

git submodule update --init

If you are distributing intervalxt or you are a purist who only wants to interact with autotools directly, then you should skip to the next section. Otherwise, we strongly recommend that you install pixi and then use the following commands:

• pixi run test build intervalxt and run the libintervalxt and pyintervalxt test suites
• pixi run compile-commands to generate a compile_commands.json that your IDE might be able to use to make sense of this project

Build from the Source Code Repository or a Tarball

If you have cloned the source directory and you decided not to use pixi, you will need to setup the configure script and Makefile using autotools. That is

git submodule update --init
./bootstrap

If you obtained a tarball of the sources or if the preceding step worked, you can now run

./configure
make
make check  # to run our test suite
make install  # to install into /usr/local

If you happen to have any of the dependencies installed in a non standard directory, you will have to specify the CPPFLAGS and LDFLAGS variables for the configure script

./configure CPPFLAGS=-I/my/path/include LDFLAGS=-L/my/path/lib

For best performance run CFLAGS="-O3" CXXFLAGS="-O3" ./configure instead of ./configure. You might want to add -g3 to CFLAGS and CXXFLAGS which does not hurt performance but gives a better debugging experience. For the best debugging experience, you might want to replace -O3 with -Og or even -O0 but the latter results in poor performance.

If your compiler supports it, you can try to add -fvisibility=hidden -fvisibility-inlines-hidden to your CXXFLAGS. This hides internal bits in the resulting library which have lead to crashes in the past due to conflicting header-only libraries.

If your linker supports it, you should use ./configure --with-version-script to shrink the resulting shared library to an exact curated list of versioned symbols.

perf works well to profile when you make sure that CFLAGS and CXXFLAGS contain -fno-omit-framepointer. You can then for example run our test suite with perf record --call-graph dwarf make check. Apart from perf itself there are several ways to analyze the output, hotspot might be the most convenient one at the time of this writing.

For more detailed but generic instructions please refer to the INSTALL file.

How to Cite This Project

If you have used this project in the preparation of a publication, please cite it as described on our zenodo site.

Acknowledgements

• Julian Rüth's contributions to this project have been supported by the Simons Foundation Investigator grant of Alex Eskin.

Maintainers

• @saraedum
• @videlec