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,
A preprint of this paper can be downloaded
here: [ PDF ]
[ PS ]
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.
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
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
This program mwattr
uses the CHomP
and CAPD software libraries,
both publically 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)
is available here: capd-lib.zip,
Note that these files only contain the core part of the C++ libraries,
which is sufficient to compile the program mwattr,
but does not contain any additional material (like documentation,
sample programs, examples, or utilities).
4. A note on decompressing the ZIP files
Please, note that all the compressed files available for download
directly from this Web page must be unzipped
in Unix/Linux/MacOS 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).
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
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
- '@' 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
- '-' 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.