Parallelization Method for a Continuous Property
Software and Examples

This page contains the software and examples referred to in the paper Parallelization method for a continuous property by Paweł Pilarczyk, published in Foundations of Computational Mathematics, DOI: 10.1007/s10208-009-9050-8.

A preprint of this paper can be downloaded here: [ PDF ] [ PS ]

A. Software

The software for computations described in the paper is written in the C++ programming language for optimal effectiveness and flexibility, and is briefly described below.

0. Files for download

Here are all the files for download referred to at this page:

  • mwattr.zip – an advanced application example (updated version) that uses both CHomP and CAPD software libraries (see below)
  • chomp-lib.zip – source code of part of the CHomP software library containing the Parallel Computations Framework (updated version),
  • capd-capdDynSys-4.2.153.zip – source code of the entire CAPD-DynSys subproject of the CAPD library, copied from the CAPD download site (compatible with the updated version of mwattr).

The original files made available when the paper was published are listed here:

  • mwattr.zip – an advanced application example (old version)
  • capd-lib.zip – an extract from the CAPD software library (old version),
  • chomp-lib.zip – an extract from the CHomP software library (old version).
Please, note that the old source code may not compile with the modern compiles anymore, due to changes in the C++ standard.

1. Parallel computations framework

The core part of the parallel computations framework, including some most basic examples and demonstrations, has been integrated with the Computational Homology Project software (CHomP) available for download at http://www.pawelpilarczyk.com/chomp/. The specific definitions are gathered in the chomp::multiwork namespace, and the interface is contained in files located in the subdirectories include/chomp/multiwork/, src/multiwork/. Two simple demonstration programs are in the programs/mwdemo/ subdirectory of the full version of the CHomP source code package.

2. Advanced application

The file mwattr.zip contains the source code of the advanced application program for the computation of a lower bound for the set of parameters of a dynamical system for which the existence of more than one attractor can be proven, as discussed in the paper. This file 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 Windows, or in Unix/Linux/MacOS. A relatively recent version of the compiler is required to compile the code correctly. The provided makefile must be adjusted before the compilation (see explanations therein). This package also contains a script dat2cell.pl for extracting uniformly rescaled lists of cells for which the computations succeeded from the files saved by the subdivision algorithm, and for plotting the computed sets of cells in a BMP file using the program cell2bmp form the CHomP software package. This script was actually used for preparing the illustrations contained in the paper.

3. The CHomP and CAPD libraries

The program mwattr uses the CHomP and CAPD software libraries, both publicly available under the terms of the GNU General Public License. Please, refer to the websites of those libraries for the source code and compilation instructions. Since these two 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 (which were actually used in the computations made for the paper) are provided for download in subsection 0 above. Note that the files provided here (especially the CHomP library extract) may only contain part of the C++ libraries, which is sufficient to compile the program mwattr, but without any additional material (like documentation, sample programs, examples, or utilities).

4. A note on decompressing the ZIP files

Please, note that it may be necessary to unzip all the compressed files available for download directly from this Web page in the text mode to ensure the correct conversion of line endings between the Linux/Unix/Mac/Windows starndards (add the -a command line switch in case of unzipping with the Info-ZIP software).

B. Examples and Applications

The examples and applications discussed in the paper are briefly described below, and the actual log and data files are also provided, together with high-resolution pictures.

1. Data format

The data available for download consists of files with the extension .dat which contain the results of computations saved by the program running as the coordinating process, and also one or more files with the extension .log which contain the text output of the programs captured from the console screen while running the computations. In this section the format of this data is explained.

1. Each line in the text data file containing the results begins with a special character that indicates the type of the information contained there:

  • Comment: ';' followed by the message.
  • Data sent for processing: '+' followed by the number of the data chunk sent in the program's run, and then by the Cartesian product of intervals sent for processing. Note that the real numbers displayed are rounded to a few significant digits only.
  • Result received from processing: '*' or '@' followed by the number of the data chunk, then the obtained result, then the level of subdivisions, and the integral coordinates of the minimal vertex of the cube to which this result corresponds. '*' indicates a full box, '@' indicates a probe.

An example of data that can appear in this file:

  • + 25 [16,32]x[-16,0].
  • * 25 0 3 (5,3).
The meaning of these lines is as follows:
  • the box [16,32] x [-16,0] was sent for processing; the number of the data chunk corresponding to this box is 25
  • a result of processing the above-mentioned data chunk (no. 25) has been received from processing; the result of the processing is 0, and the box corresponds to the cube [5,6] x [3,5] at the third subdivision level

2. The syntax of lines displayed on the terminal by the coordinator:

  • '+' followed by an integral number and the dot: The data chunk with this number has been prepared to be sent for processing.
  • '*' followed by two integral numbers and the dot: The data chunk with the first number has been received from processing, and the second number shows the obtained result.
  • '!' followed by a message: An error occurred. The message explains what happened.
Additional messages are only displayed if the command-line switch --debug is used and they indicate detailed actions taken by the subdivision algorithm. A brief description of most common messages is provided below; please, see the source code file include/chomp/multiwork/mwsubdiv.h for details.
  • '@' followed by 'GoodProbe', 'NegProbe', 'SuccessBox' or 'FailedBox' indicates processing a good probe, negative probe, successful box, or failed box, respectively. The subdivision level is indicated in brackets, and the integral coordinates of the corner with minimal coordinates (the left bottom corner) with respect to this subdivision level follow.
  • '+' followed by 'Good' or 'Waiting' indicates adding a good probe to the known results or putting a box to the queue of boxes waiting for verificaiton, respectively. The coordinates of the box are given as above.
  • '-' followed by 'Waiting' or 'Test' indicates the removal of a box or a probe, respectively, from the corresponding queues of elements awaiting verification. The coordinates are given as above.

3. The syntax of lines displayed on the terminal by a worker, or by the coordinator if the data is processed locally:

  • '-' followed by an integral number and the dot: The data chunk with this number has been received for processing.
  • '=' followed by two integral numbers and the dot: The data chunk with the first number has been processed, and the second number indicates the result.
  • '!' followed by a message: An error occurred and the data has been rejected. The message explains what happened.

2. Approximations of the ring

The file mwcircle.zip contains the results of computations for the five subsequent approximations of the ring discussed in the paper, and one additional approximation as well. The .dat and .log files are included. The illustrations of these approximations of the ring obtained with the script dat2cell.pl and the program cell2bmp are depicted below (click each thumbnail for a full-size picture).

Note that in these pictures, as well as in the picture below, extra space has been added between squares of various sizes which together form a connected set, in order to clearly visualize the sizes of these squares.

3. Multiple attractor hunt

The file mwattr12.zip contains the results of computations run on a single computer equipped with two Intel DualCore Xeon5030-2.66GHz processors, with the subdivision depth limit set to 12 and with additional information turned on, just like in the script runlocal included in the file mwattr.zip. The computations took almost 3.5 hours, and the actual processor time used by each process is provided at the end of each log file.

The picture below is a miniature of the actual illustration of the computed lower bound for the region of parameters for which the existence of more than one attractor has been proved. Please, click the picture to see the full image which is of the size of 2003x4091 pixels.