Expansion in One-Dimensional Dynamics

Software and Data

This page contains software and results of the computations referred to in the paper Rigorous computation of expansion in one-dimensional dynamics by Paweł Pilarczyk, Michał Palczewski and Stefano Luzzatto.

For a preprint of this paper, see arXiv:2505.20495.

Files for Download

The algorithms described in the paper are implemented in C++. The software is published here under the terms of the GNU General Public License, version 3+. The source code of the software is prepared to be compiled with the GNU C++ compiler in Linux, but it might be possible to compile it in a different system, possibly after some minor modifications. The source code contains comments in a format that allows one to generate documentation with the Doxygen software.

Below is a list of files for download (please, see the description in the next sections). The zipped files should be uncompressed to empty subdirectories (folders), except for capd-capdDynSys-4.2.153.zip, which already includes a subfolder. Please, note that in Windows these files should be unzipped in the text mode to ensure the correct conversion of line endings (add the -a command-line switch in case of unzipping with the Info-ZIP software).

unifexp-src.zip – source code of the software,
capd-capdDynSys-4.2.153.zip – source code of the entire CAPD-DynSys subproject of the CAPD library, copied from the CAPD download site,
capd4fix.zip – a fix for the CAPD library files,
chomp-lib.zip – source code of part of the CHomP software library.
unifexp-add.zip – additional files such as raw data files and scripts for running selected computations and creating some figures.

Software

The software for computations described in the paper is written in the C++ programming language for optimal effectiveness and flexibility. It consists of some classes and functions that can be used from within other programs, and also one executable program unifexp that can be called from a terminal (or from a script) with appropriate command-line arguments. Run this program without arguments for brief explanations.

The file unifexp-src.zip containing the source code of the software is available here for download under the terms of the GNU General Public License. It is prepared for the compilation with the GNU C++ compiler, either in GNU/Linux (or a similar system), or in Windows in the MSYS environment. A relatively recent version of the compiler is required to compile the code correctly. The provided makefile must be adjusted before the compilation, especially as far as the paths to the CAPD and CHomP libraries are concerned (please, see the explanations in the file itself).

The software uses the Boost, CHomP and CAPD libraries which are publically available, the last two under the terms of the GNU General Public License. Please, refer to the websites of those libraries for the source code and compilation instructions. Note that the Boost library is often included in standard GNU/Linux distributions, so no installation might be necessary. This is not the case with the other libraries, though. Even worse, since those libraries are undergoing dynamic development, it may turn out that their interface may slightly change in the future versions, so a copy of compatible versions of both libraries is available for download from this page (please, see the previous section).

Compilation of the Software

Step 1. Compilation of CHomP. This is my suggestion:

mkdir chomp
cd chomp
unzip -a ../chomp-lib.zip
make library
cd ..

Please, see the CHomP website for more information on the compilation of this software package.

Step 2. Compilation of CAPD. Since this library has many options, here is my suggestion for how to compile it. Note that it may be necessary to install the additional package pkg-config if it is not present in the system.

unzip -a capd-capdDynSys-4.2.153.zip
mkdir capd4
mkdir capd4_compil
cd capd4_compil
../capd-capdDynSys-4.2.153/configure --prefix /home/your-dir/capd4 --with-filib=yes --with-mpfr=no --with-boost=/usr --without-gui
make
make install

Please, see the CAPD website for more information on the compilation of this software package.

Step 3. Applying a patch to the CAPD library files. After having successfully compiled the CAPD library, my suggestion is to replace a few files in order to avoid some errors and warnings that appear while compiling the main program:

mkdir capd4fix
cd capd4fix
unzip -a ../capd4fix.zip
sh ./_capd4fix.sh

Step 4. Compilation of the unifexp program. After having successfully compiled the CHomP and CAPD libraries, this is my suggestion on how to proceed:

mkdir unifexp
cd unifexp
unzip -a ../unifexp-src.zip
make

Step 5. Testing the program. You can run a test computation to see if the program works:

./unifexp -p cycle10p2n0 -m minus-quadratic-intv -a 1.99 -a 1.99 -k 1001 -d 0.001 --rigorous --lambda -i -L 0 -L 0 --debug

Some useful additional command-line arguments (used in other scripts) are:
--log filename.log — save the program's output additionally to a file,
-f filename.csv — save the results of computations for many parameters to a file. Note: This file is read before running the computations in order to skip parameters processed before.

Data Format

These results of comprehensive computations run by the software described in the previous sections are saved by the unifexp program in a CSV text file. The first line contains comma-separated titles of columns, and the next lines contain the following items as a comma-separated list of values:

level — the level of subdivision of the parameter interval (e.g. 10 for 2¹⁰=1024 subintervals)
num — the identifier of the data piece in the collection at the given subdivision; the identifiers begin with 0
parMin — the left endpoint of the parameter interval (minimal parameter value)
parMax — the right endpoint of the parameter interval (maximal parameter value)
k — the total number of intervals on which the graph representation of the map was built (the intervals that form the critical neighborhood are counted here, too)
delta — the radius δ of the critical neighborhood
lambda — the computed expansion exponent λ
logC — log C if the constant C was computed (see the 2008 paper), otherwise 0
lambda0 — the constant λ₀ if it was computed (see the 2008 paper), otherwise 0
period — the period of a periodic orbit found (0 if none)
lambdaMax — an upper bound on the expansion exponent of the periodic orbit found (0 if none)
distFrom0out — the minimum guaranteed distance of the periodic orbit from 0
distFrom0in — an upper bound on the distance from 0 during the closest approach to 0
compTime — the computation time measured in seconds

Results of Computations

The file unifexp-add.zip contains scripts for running the computations discussed in the paper, as well as the results of such computations. It includes, in particular, raw data with the results of comprehensive computations conducted for full ranges of parameters split into smaller sub-intervals or for individual values of parameters within the given ranges, used to create the figures published in the paper. The scripts and data files are described below.

A general hint on gathering statistics on the computations: The Python script read_unifexp_dat.py called with a CSV file produced by the unifexp program shows a preview of the data and the total CPU time used for the computations. This script can also be used as a Python module that reads the data from the CSV file to a DataFrame object with appropriate data types.

example1 — Scripts and resulting data for the examples discussed at the beginning of Section 4.1 Comparison of the new method against the previous approach are provided in the files example1* in the unifexp-add.zip archive. Please, see the individual shell files for the command line and the log files for the results of computations. Note the partition type used, its size, and the parameter values.

example2 — Script and log files for the computation for a=1.94082 discussed at the end of Section 4.1. In this specific example, our method provides an outstandingly better result that the previous approach, as explained in the paper.

splitting — Scripts and resulting data for Figure 6 that shows the location of intervals split by the algorithm during the first 100 iterations.

run20 — Scripts and resulting data for Figure 1 that shows the difference between the exponent λ computed with our new method (using dynamically refined partitions) and with the previous approach (using a uniform partition). The scripts run20a.sh (for the new method) and run20b.sh (for the previous approach) run the computations, and the Python script lambda_compare.py can be used to gather the information discussed in Section 4.1 Comparison of the new method against the previous approach. Published open data: run20a.csv and run20b.csv.

lambdaMax — Scripts and resulting data for Figure 7 that shows the difference between λ_max and λ discussed in Section 5.2 on the optimality of our approach. The script lambdaMax.sh conducts the computations and generates the data file lambdaMax.csv, and the Python script lambda_vs_lambdaMax.py computes the various statistics provided in the paper, and plots the pie diagram shown in the paper. Analogous computations for full intervals of parameters, as opposed to individual values, are conducted with the script lambdaMaxi.sh that produces the file lambdaMaxi.csv. Published open data: lambdaMax.csv.

run20e00–03 — Scripts for running a series of computations discussed in Section 4.2 on the dependence of expansion on the size of the critical neighborhood. The computations are as follows:
– run20e00: δ=0.001, k=3000
– run20e01: δ=0.1, k=1000
– run20e02: δ=0.01, k=1000
– run20e03: δ=0.001, k=1000
The statistics discussed in Section 4.2 of the paper were gathered by the Python script lambda_compare.py. Published open data: run20e00-03.zip.

run20e10–27 — Scripts for running a series of computations for intervals of parameters as opposed to individual parameter values, discussed in Section 4.3. All the computations were done for δ=0.001 and k=1000. Computations 10–17 were run for the parameter interval [1.4,2] split into 10¹⁰, ..., 10¹⁷ parameter subintervals, and computations 21–27 were run for 10¹¹+1, ..., 10¹⁷+1 individual parameter values. Note that the missing computation no. 20 is the same as the one called run20a described above. Published open data: run20e10-27.zip.

run20d00–09 — Scripts for running a series of computations discussed in Section 4.4 in which our approach is compared against the derivative-based method suggested in an earlier paper. The computations are conducted for the 7 different strategies discussed in the paper for partitioning the complement of the critical neighborhood into k=5000 intervals whose width depends on the derivative of f_a, including the uniform partition (no. 0, no dependence) and the obviously wrong partition (no. 9, numbered –1 in the paper). Published open data: run20d00-09.zip.

plot_graphs.py — Script for creating most pictures in the paper. It reads the CSV data sets and produces figures that it saves to a few different files.

Acknowledgments

This research was supported by the National Science Centre, Poland, within the grant OPUS 2021/41/B/ST1/00405. Some computations were carried out at the Centre of Informatics Tricity Academic Supercomputer & Network.