Algorithms¶
tidynamics relies on the Fast Correlation Algorithm (FCA) that was proposed in the context of molecular simulations by Kneller et al [KKKS95] and that was included in the software nMOLDYN. For the full explanation, see the article or nMOLDYN’s user manual. We provide here an overview of the algorithms.
The FCA results in the same numerical values for correlation functions as running explicitly an average over all pairs of points at a computational cost of \(O(N \log N)\) instead of \(O(N^2)\) where \(N\) is the length of the time series. For a brief illustration of correlation algorithms, see this blog post http://pdebuyl.be/blog/2016/correlators.html
By using NumPy for all operations, the overhead of using an interpreted language is reduced and the advantage of the FCA in terms of computational complexity makes is feasible to analyze realistic datasets in memory, for instance in an interactive IPython terminal or a Jupyter notebook.
Correlations¶
The correlation \(C_{AB}(\tau)\) is
where the angle brackets denote an average over time.
For correlations, the FCA relies on a slight modification of the Convolution theorem in which one convolves a time series with its time-reversed counterpart.
One important point of attention in the algorithm consists in padding the data with zero values, as else the result contains the correlation of the signal with its periodic image.
Mean-Square Displacements¶
The mean-square displacement \(MSD(\tau)\) is
where the angle brackets denote an average over time.
The computation of the MSD relies on decomposing the average into an average term and an explicit correlator:
The correlator is computed with the convolution theorem and the other operations have linear complexity. The finite length of the time series is also taken into account in the algorithm.
Cross displacements¶
The cross displacement [KWtH+13] \(C_{ij}(\tau)\) is
As for the mean-square displacement, the interest of using tidynamics lies in the fast computation of the correlation part.