1. Introduction and goals

CMlib is a library of cell mapping algorithms and utility functions and classes written in c++. Cell mapping methods are suitable for the global analysis of dynamical systems, they can be used to efficiently find state space objects (fixed points, periodic orbits and their corresponding domains of attractions) in a given discretized state space domain.

The goal of the CMlib library is to provide simple and efficient implementations of basic cell mapping algorithms allowing users to quickly utilize them to their problems or to integrate them into other applications independently of the underlying data types or differential equation solvers. To achieve this, CMlib mostly provides template base classes for various components, from which application-specific classes can derived.

The target audience of this library (and the included cell mapping methods) ranges from university students to researchers, as these methods can be used to demonstrate the behaviour of simple systems or to analyse the state space of complex, non-linear, but usually low-dimensional systems.

The author of the CMlib library have used cell mapping methods extensively during his PhD studies and currently moving (and rewriting) his private code base to this open-source library.

2. Features

• Current version includes Simple Cell Mapping (SCM) [1] and Clustered SCM [2] methods, Generalized Cell Mapping (GCM) will be added.
• Entirely written in C++ considering modern language features, with care to code clarity and documentation.
• Contains cross-platform and efficient implementations of cell mapping algorithms.
• Template approach allows replacing certain components (e.g., underlying data types, methods for state space discretization, used solvers) easily and independently from each other.
• Open source (with MIT licence), hosted on GitHub.
• Actively maintained and developed.

3. Documentation

The CMlib library is hosted on GitHub at: github.com/Gyebro/cell-mapping. Doxygen generated code documentation (description of classes, APIs) can be found at the GitHub page of the repository: gyebro.github.io/cell-mapping.

The latest version of this guide is available in the cell-mapping/docs folder of the repository. The repository's main page contains information about the currently developed features which can usually be found on development branches.

4. Installation

4.1. Requirements

The CMlib library can be used as a stand-alone C++ library built from sources contained in the cpp/cm folder of the repository or as a CMake library. The only requirement is a modern C++ compiler with C++11 support. (GCC 4.8.1 or above, on Windows, MinGW-w64 is recommended.)

For convenience and to aid cross-platform compilation, a CMake project is provided, and it is recommended to compile the library (and demonstrations) using CMake (available at cmake.org.) Alternatively, one can use an Integrate Development environment which supports CMake projects, such as JetBrains CLion (which is available for free to university students and faculty at jetbrains.com/clion).

4.2. Cloning the repository and building the demonstrations

Cloning the CMlib repository can be done with git, or alternatively, by simply downloading the repository as a zip archive.

The top level CMakeLists.txt file can be found in the cell-mapping/cpp folder. For convenience, scripts for reloading the CMake project (reload-project-* files) and building the demonstrations (build-demo-* files) are provided.

In order to build the demonstrations on Windows in Release mode, run: reload-project-release.bat, followed by build-demo-release.bat. To build on Linux, use the same files with .sh extension.

After building, demonstration executables can be found in the cmake-build-release/demo folder.

Command line summary:

git clone https://github.com/Gyebro/cell-mapping.git	Clone the repository
cd cell-mapping/cpp	Change to project dir
reload-project-release.bat	Reload project in Release
build-demo-release.bat	Build demonstrations
cd CMake-build-release/demo	Change to build dir
demo-pendulum	Run the pendulum demo

5. Examples

Some simple examples are provided in this section to show the basic concept and usage of the cell mapping library.

5.1. Simple pendulum

Consider the equation of motion of a simple pendulum with damping \(\delta\) and stiffiness originating from the gravity (characterised by \(\alpha\)):

\( \ddot{\varphi}(t) + \delta \dot{\varphi} (t) + \alpha \mbox{ sin}(\varphi(t)) = 0 \)

(1)

In order to execute Simple Cell Mapping (SCM) on a dynamical system, first a class should be derived from DynamicalSystemBase:

1  class Pendulum : public cm::DynamicalSystemBase<vec2> {
2   private:
3    double alpha; // Stiffness
4    double delta; // Damping
5    double dt;    // Target integration time for a "step"
6   public:
7    Pendulum (double alpha, double delta, double timestep) :
8     alpha(alpha), delta(delta) { dt = timestep; }
9    vec2 f(const vec2 &y0, const double& t) const {
10    return vec2({
11     y0[1],
12     -delta*y0[1] -alpha*sin(y0[0])
13    });
14   }
15   vec2 step(const vec2 &state) const override {
16    // Use RK45 to integrate the system scheme
17    cm::RK45<vec2,Pendulum> rk45(this, 1e-8);
18    return rk45.step(state, 0, dt, dt/50.0);
19   }
20 };

The DynamicalSystemBase class requires a step function which can be used to track trajectories of the system. In order to generate a solution, the RK45 template integrator can be used (see lines 17-18). To use the solver, the function f(y0,t) needs to be implemented in the Pendulum class which describes the right-hand side of the system written as a set of first order differential equations (see lines 11-12). Note: vec2 is a simple 2-element vector type provided by the library.

In order to execute SCM on the Pendulum system, the center, width and cell counts of the state space along state-space dimensions should be defined. In CMlib, the state space region of interest is defined by its center point and its width according to Figure 1.

1  int main () {
2   Pendulum pendulum (1.0, 0.2, 0.1);
3   // Cell state space properties
4   vec2 center = {0.0, 0.0};
5   vec2 width = {16.0*M_PI, 10.0};
6   vector<uint32_t> cells = {1400, 800};
7   // SCM object and solution
8   SCM32<vec2> scm(center, width, cells, &pendulum);
9   scm.solve(20); // Max. number of steps to leave state-space cells
10  scm.generateImage("pendulum.jpg");
11  return 0;
12 }

Figure 1. The definition of state space region in \((x, x')\) based on its center c and width w with cell count vector z.

The SCM32<StateVectorType> class' template parameter in this case is vec2 as the Pendulum used that type for the state vector. Note: SCM32 is a type definition for SCM<SCMCell<uint32_t>, uint32_t, StateVectorType> meaning, that the addressing of cells are done with 32-bit unsigned integers. If your state space contains more than \(2^{32} - 1 = 4\) GCells, use SCM64 instead.

After running this example program, the following output is generated:

Figure 2. pendulum.jpg: the \((\varphi, \dot{\varphi})\) state space of the simple pendulum. Coloured regions indicate domains of attraction of stable equilibria -- fixed points.

Related files: demo-pendulum.cpp, pendulum.h in the demo folder.
Exercise: Modify the damping parameter of the example and see how the state-space changes.

5.2. Micro-chaos map

Consider a PD-controlled 1 DoF inverted pendulum, where the quantized control force is calculated at sampling intervals \(\tau\) (zero-order hold). According to the solution of the linearised, dimensionless equation of motion, the following so-called micro-chaos map can be derived between the states at subsequent sampling instants:

\( \mathbf{y}_{i+1}=\mathbf{U}\,\mathbf{y}_i+\mathbf{b} \,F_i, \)

(2)

where \(F_i=\mathrm{Int}(\hat P x_{i}+\hat D x'_{i})\), \(\mathbf{y}=[x_i\quad x'_i]^T\), and:

\(\begin{equation} \mathbf{U}=\frac{e^{-\hat{\alpha} \delta}}{\Gamma} \left[ \begin{array}{cc} \Gamma \cosh \left(\hat{\alpha } \Gamma \right)+\delta \sinh \left(\hat{\alpha } \Gamma \right) & \sinh \left(\hat{\alpha } \Gamma \right)/\hat{\alpha } \\ \hat{\alpha } \sinh \left(\hat{\alpha } \Gamma \right) & \Gamma \cosh \left(\hat{\alpha } \Gamma \right)-\delta \sinh \left(\hat{\alpha } \Gamma \right) \\ \end{array} \right], \nonumber \end{equation}\)

\(\begin{equation} \mathbf{b}=\frac{1}{{\hat\alpha}^2 \Gamma}\left[\begin{array}{cc} \Gamma -e^{-\hat{\alpha } \delta } \left(\Gamma \cosh \left(\hat{\alpha } \Gamma \right)+\delta \sinh \left(\hat{\alpha } \Gamma \right)\right) \\ -\hat{\alpha} e^{- \hat{\alpha } \delta }\sinh \left(\hat{\alpha } \Gamma \right) \end{array}\right] \nonumber \end{equation}\)

where \(\Gamma=\sqrt{1+\delta^2}\), and \(\hat{\alpha}\) is the dimensionless stiffness, \(\delta\) is the relative damping and \(\hat{P}, \hat{D}\) are the dimensionless control gains. \(\mathrm{Int}()\) denotes taking the integer part of the calculated control effort, and thus introduces switching lines for every integer value.

This system is implemented in the microchaos.h/cpp files in the demo folder of the repository. The system class needs to implement the step function of the DynamicalSystemBase class.

1 vec2 MicroChaosMapStatic::step(const vec2& y0) const {
2  double F = SymmetricFloor(k*y0); // Rounding at output, k = {P,D}
3  vec2 y1 = U*y0 + b*F;            // The micro-chaos map
4  return y1;
5 }

To apply SCM on this problem, consider the following code snippet:

1  int main() {
2   double P = 0.007;        // Parameters and system
3   double D = 0.02;
4   double alpha = 0.078;
5   double delta = 0;
6   MicroChaosMapStatic system(P, D, alpha, delta);
7   vec2 center = {0, 0};    // State-space properties
8   vec2 width  = {2400, 50};
9   vector<uint32_t> cells = {1000, 400};
10  SCM32<vec2> scm(center, width, cells, &system); // SCM
11  scm.solve(20);
12  scm.generateImage("scm-microchaos.jpg");
13  return 0;
14 }

After successful execution, the following output image is generated:

Figure 3. SCM results for the micro-chaos map. Coloured regions indicate domains of attraction of chaotic attractors (white cell groups along the \(x\) axis).

Related files: demo-microchaos.cpp, microchaos.h/cpp in the demo folder.

Exercise: Increase the cell count in the example and see how the tiny details of the state space reveal themselves.

Note: a 4 gigapixel image (corresponding to 4 billion cells, close to the limit of the 32bit unsigned integer address) of this example is hosted at: mm.bme.hu/~gyebro/scm/.

5.3. Duffing oscillator

Consider the Duffing equation:

\( \ddot x(t) + \delta\,\dot x(t) + \alpha x(t) + \beta x^3(t) = \gamma\,\cos(\omega\,t) \)

(3)

The implementation of this dynamical system can be found in the duffing.h file. In this example SCM is applied to generate a Poincaré-section of this system by choosing integration time to \(T = 2\,\pi / \omega\).

Consider the following code snippet:

1  int main() {
2   double alpha = -1.0;      // System and its parameters
3   double beta  = 1.0;
4   double gamma = 0.28;
5   double delta = 0.3;
6   double omega = 1.2;
7   double T = 2*M_PI/omega;
8   DuffingOscillator duffing(alpha, beta, gamma, delta, omega, T);
9
10  vec2 center = {0.0, 0.0}; // Cell state space properties
11  vec2 width  = {4.0, 3.0};
12  vector<uint32_t> cells = {1000, 1000};
13
14  SCM32<vec2> scm(center, width, cells, &duffing);
15  // Declare an alternate coloring method
16  SCMBlackAndWhiteColoring<uint32_t> coloringMethod;
17
18  // Execute SCM with different gamma values
19  vector<double> gammas = {0.28, 0.29, 0.37, 0.5};
20  for (double g : gammas) {
21   duffing.setGamma(g);
22   scm.solve(20);
23   string imageName = "scm-duffing-gamma="+to_string(g)+".jpg";
24   scm.generateImage(imageName, &coloringMethod);
25  }
26  return 0;

Upon successful execution, multiple output images show some characteristic Poincaré-sections of the Duffing equation.

Figure 4. SCM results for the Duffing oscillator's Poincaré-section at \(\gamma = 0.5\).

Related files: demo-duffing.cpp, duffing.h in the demo folder.

Exercise: Run the demo and examine the other outputs. Play with the state space resolution and other system parameters.

References

[1]   C. S. Hsu, Cell-to-Cell Mapping: A Method of Global Analysis for Nonlinear Systems, Springer, Singapore, Applied Math. Sciences, 64, 1987. DOI: 10.1007/978-1-4757-3892-6.

[2]   G. Gyebrószki and G. Csernák, Clustered Simple Cell Mapping: An extension to the Simple Cell Mapping method, Communications in Nonlinear Science and Numerical Simulation 42, pp. 607–622, 2017. DOI: 10.1016/j.cnsns.2016.06.020.