# Weakly Coupled Distributed Calculation of Lyapunov Exponents for Non-Linear Dynamical Systems
## 3 Parallel Application Design
### MPI Distributed Implementation  
One of the big advantages of using MPI is that it is a standard for coding message-passing based applications ([PERSON] _et al._, 2017). Although there exist some other message-passing implementations, like Java Parallel Virtual Machine (JPVM) [[http://www.cs.virginia.edu/ajf2j/jpvm.html](http://www.cs.virginia.edu/ajf2j/jpvm.html)]([http://www.cs.virginia.edu/ajf2j/jpvm.html](http://www.cs.virginia.edu/ajf2j/jpvm.html)) (KBasically, the computational problem consists in solving the system of Equations (1)-(6) for very large times, which in our case turns into the solving of a huge amount of subproblems with the fourth-order Runge-Kutta (RK) method. This occurs by slightly varying the initial conditions in each RK calling to determine the Lyapunov coefficient between such two initial conditions. One of the first tactics one might think of to solve the problem is that it could be addressed by carrying out the parallelisation of the Runge-Kutta method, for which a series of procedures already exists for shared memory architectures [13], as well as for technologies such as the Xeon Phi [14] and Graphic Processing Units (GPUs) [15]. There are also options for Runge-Kutta parallelisation using MPI [16], but they are not good options considering the network's latency. Thus, the best strategy is to disrupt the \(N\) (RK) problems that should be solved, and analyse the dependencies.  
By analysing the algorithm, we see that it is necessary to execute \((N-1)\) Runge-Kutta instances for a different set of initial conditions \(\left\{C_{n}\right\}_{n=0}^{N}\). Obviously, in the serial implementation, the recalculation of the Runge-Kutta method is avoided by storing the previous adjacent result (in initial condition); that is, once the Lyapunov coefficient is calculated between \(C_{i-1}\) and \(C_{i}\), the calculation of \(C_{i}\) is no longer necessary to obtain the Lyapunov coefficient between \(C_{i}\) and \(C_{i+1}\) in the next iteration \(\forall i(0<i<N)\). Therefore, in this way, the algorithm has no strong dependencies rather than the adjacent ones, i.e., is weakly coupled.  
To divide tasks in a balanced way, we follow the procedure described by [PERSON] et al. [17], and [PERSON] et al. [18]. Let \(p_{n}\) be the number of MPI processes and \(C_{n}\) the number of problems to solve, then we define the problem number with which a process, \(p\), must start and finish as \(p_{s}\) and \(p_{e}\), respectively. To determine \(p_{s}\) and \(p_{e}\) in each process, \(p\), we proceed as follows:  
\[s :=\left\lfloor C_{n}/p_{n}\right\rfloor, \tag{10}\] \[r :=C_{n}(\bmod\,p_{n}). \tag{11}\]  
Therefore  
\[p_{\text{start}}:=p\times s+1 \tag{12}\]  
and  
\[p_{\text{end}}:=(p+1)\times s. \tag{13}\]  
If \(r\
eq 0\) and \(p<r\), then we make an adjustment as:  
\[p_{\text{start}}:=p_{\text{start}}+p \tag{14}\]  
and  
\[p_{\text{end}}:=p_{\text{end}}+(p+1). \tag{15}\]  
If \(r\
eq 0\) and \(p\geq r\), then:  
\[p_{\text{start}}:=p_{\text{start}}+r \tag{16}\]  
and  
\[p_{\text{end}}:=p_{\text{end}}+r. \tag{17}\]  
In this way, the number of problems to be solved (distributed) in the nodes is thus divided: because the previous problem must be calculated together with the present (except for the process \(p_{0}\)), it is necessary that \(p_{\text{start}}\) be decremented by \(1\). Therefore, \(p_{\text{start}}=p_{\text{start}}-1\) for all processes from \(p_{1}\) to \(p_{n}\).