# Performance of calculation of mean squared displacement

How can I improve the performance of the following code which calculates the mean squared displacement for coordinates stored in data? Here for each time difference dn all possible distance combinations are taken into account:

---- distance combinations between points
dn=1: 1 and 2, 2 and 3, 3 and 4, ... n-1 and n
dn=2: 1 and 3, 2 and 4, 3 and 5, ... n-2 and n-1
dn=3: 1 and 4, 2 and 5, 3 and 6, ... n-3 and n-2
...


and so on ...

data = Import["data.txt"]; (*data file: http://goo.gl/Fmm9fZ*)
msd = Array[0 &, {n - 1, n - 1}];
xSquared = Array[0 &, {n - 1, n - 1}];
ySquared = Array[0 &, {n - 1, n - 1}];

Table[
dx = data[[n + dn, 1]] - data[[n, 1]];
dy = data[[n + dn, 2]] - data[[n, 2]];
msd[[dn, n]] = dx^2 + dy^2;
xSquared[[dn, n]] = dx^2;
ySquared[[dn, n]] = dy^2,
{dn, 1, n - 1},
{n, 1, n - dn}
]; // AbsoluteTiming


Is something else possible?

Later on the mean of the arrays msd, ySquared and ySquared is calculated taking into account that of each dn the relevant length is n-dn.

Table[
msdMean[[dn]] = Mean[msd[[dn, 1 ;; n - dn]]];
msdStdDev[[dn]] = StandardDeviation[msd[[dn, 1 ;; n - dn]]];
xSquaredMean[[dn]] = Mean[xSquared[[dn, 1 ;; n - dn]]];
xSquaredStdDev[[dn]] =
StandardDeviation[xSquared[[dn, 1 ;; n - dn]]];
ySquaredMean[[dn]] = Mean[ySquared[[dn, 1 ;; n - dn]]];
ySquaredStdDev[[dn]] =
StandardDeviation[ySquared[[dn, 1 ;; n - dn]]],
{dn, 1, n - 2}
];


My notebook which I used to calculate and plot them is here: http://goo.gl/ztPqxN

Update for FFT solution:

https://stackoverflow.com/questions/34222272/computing-mean-square-displacement-using-python-and-fft

FFT-Code in Python:

1. https://github.com/soft-matter/trackpy/blob/master/trackpy/motion.py

2. the MSD should be done by looking at non-overlapping windows of a given time and then averaging those. There was some recent work (github.com/soft-matter/trackpy/pull/337) to make msd computations faster.

How to get errors (standard deviation of mean value data set):

1. see github.com/soft-matter/trackpy/pull/352 for discussion of computing errors on the msd.

UPDATE:

Please use for your code my data file: http://goo.gl/Fmm9fZ

I am very much interested that the numerical results of my code can be reproduced and that for the whole set of calculations I did (three mean value data sets and their errors) the performance is compared.

• It might help if you added some words explaining what exactly you're expecting the code to do. – Martin Ender Apr 7 '16 at 21:05
• it is correctly calculating the mean squared displacement of 2d coordinates saved in data ... but very slow – mrz Apr 7 '16 at 21:10
• Then I guess it might be a dupe of either this or this whose answers contain code to compute the mean squared displacement. I haven't timed those to see how they fare compared to your implementation though. – Martin Ender Apr 7 '16 at 21:13
• @Martin Büttner: Both answers you mention are treating only a part of of what is physically needed (they do not average over all possible time differences). The upper code has been tested for real particle coordinates and corresponding results are correct and published ... I need just performance tuning help. – mrz Apr 7 '16 at 21:29
• Subscripting is generally thought to be slow and you are doing a LOT of subscripting, but it looks like you are tending to do that along rows. So, can you consider doing a Map or a Table or perhaps even Thread to generate items within each row using far fewer individual subscripts? Or just rewrite it in C and be done with it? It isn't that hard and should be orders of magnitude faster. – Bill Apr 7 '16 at 21:36

Update

My previous code had an error, it should be Total[#^2] & (sum of squares) instead of (Total@#^2) & (square of sum). The full code should look like this:

data = Import["http://goo.gl/Fmm9fZ", "Table"][[1 ;; -2]];
dx = 1.9*10.^-3; data = data*dx;
meanDisp[data_, dn_] := Mean[Total[#^2] & /@ Differences[data, 1, dn]];
meanStd[data_, dn_] :=
StandardDeviation[Total[#^2] & /@ Differences[data, 1, dn]];
meanXsq[data_, dn_] := Mean[#[[1]]^2 & /@ Differences[data, 1, dn]];
meanXsqStd[data_, dn_] :=
StandardDeviation[#[[1]]^2 & /@ Differences[data, 1, dn]];
meanYsq[data_, dn_] := Mean[#[[2]]^2 & /@ Differences[data, 1, dn]];
meanYsqStd[data_, dn_] :=
StandardDeviation[#[[2]]^2 & /@ Differences[data, 1, dn]];

{msdMean, msdStdDev, xSquaredMean, xSquaredStdDev,ySquaredMean, ySquaredStdDev} =
Table[#[data, dn], {dn, 1, Length@data - 2}] & /@ {meanDisp,
meanStd, meanXsq, meanXsqStd, meanYsq, meanYsqStd};


Update 2 We can further improve performance by exploiting the ^2 being Listable

allCalc[data_, dn_] :=
Module[{diff, x2, y2, x2m, y2m, x2s, y2s, disp, std},
diff = (Differences[data, 1, dn]^2);
{x2, y2} = Transpose@diff;
{{x2m, x2s}, {y2m,
y2s}} = {Mean[#], StandardDeviation[#]} & /@ {x2, y2};
std = StandardDeviation[x2 + y2];
disp = x2m + y2m;
{disp, std, x2m, x2s, y2m, y2s}];


We can also compile this new function:

allCalcCompile =
Compile[{{data, _Real, 2}, {dn, _Integer, 0}},
Module[{diff, x2, y2, x2m, y2m, x2s, y2s, disp, std},
(* the same body *)
], RuntimeOptions -> "Speed"];


Now if we compare performance:

{t, newCompile} =
AbsoluteTiming[
Transpose@
Table[allCalcCompile[data, dn], {dn, 1, Length@data - 2}]];
t
{t, new} =
AbsoluteTiming[
Transpose@Table[allCalc[data, dn], {dn, 1, Length@data - 2}]];
t
{t, old} =
AbsoluteTiming[
Table[#[data, dn], {dn, 1, Length@data - 2}] & /@ {meanDisp,
meanStd, meanXsq, meanXsqStd, meanYsq, meanYsqStd}];
t
(*
0.276597
0.632528
3.3952
*)

• I have to check it ... the main thing is mentioned in the beginning in my question ... for each time time difference dn another number of combinations is possible (it is decreasing with increasing dn) and therefore the averaging has to to take into account first all possible combinations and later on for the mean only the relevant existing values have to be used ... (see my update and the available notebook) – mrz Apr 7 '16 at 22:09
• @mrz this is what Differences does. Read its docs... I just discovered this function. It's amazing how much faster it is (~100 times than manual iteration) – BlacKow Apr 7 '16 at 22:11
• I can't believe it ... will check everything tomorrow .. by the way I updated my question concerning the FFT (see above). It is implemented in Pythons trackpy package: github.com/soft-matter/trackpy/blob/master/trackpy/motion.py – mrz Apr 7 '16 at 22:17
• I thinks there is a small error: imgur.com/8BAX4pe – mrz Apr 8 '16 at 0:34
• @mrz I checked that the data is the same between all three methods, and I think you mentioned that the "old" method gives correct results. Regarding further optimization I'm really confident that it's not the limit (I'm not talking about fourier method here). I would say that my knowledge is very limited and the optimization in MMA is often counter intuitive. Also compilation is kinda last thing you want to use, see here for some examples. – BlacKow Apr 16 '16 at 20:49

Here is an FFT approach for those interested.

mFFT[lis_?VectorQ] := Module[{data, acf, len = Length @ lis},
data = Join[lis, ConstantArray[0., len]];
acf = InverseFourier[Abs[Fourier @ data]^2];
acf = Re @ acf[[1 ;; len]]/Range[len, 1., -1.]]


This first half gives the position correlation function of the particle. To get the mean squared displacement we still need to compute the first and last time autocorrelation function:

msd[lis_?MatrixQ, dt_?NumericQ] :=
Module[{t, acf, d2, d = Total[lis^2, {2}], ss, msd, len = Length@lis},
ss = 2. Total[d];
Scan[(d2[# - 1] = d[[#]]) &, Range[1, len]];
d2[-1] = d2[len] = 0.;
msd = ConstantArray[0., len]; acf = Total[mFFT /@ Transpose[lis]];
msd = Table[ss = ss - d2[k - 1] - d2[len - k];
ss/(len - k), {k, 0, len - 1}]; t = Range[0., dt (len - 1), dt];
Rest@Transpose[{t, msd - 2 acf}]]


Here is how to use it:

SetOptions[#, FourierParameters -> {1, -1}] & /@ {Fourier, InverseFourier}
data = ReadList["http://goo.gl/Fmm9fZ", {Number, Number}]; (* your data *)
res = msd[data, 1/60.];

ListLogLogPlot[res]


Note that you can include the FourierParameters option in the code for meanSqD, I chose not to. For the provided dataset, it's about 3 orders of magnitude faster than OP's code and an order of magnitude faster than the Differences approach. But really, this approach begins to shine when the data is large.

• Form my point of view it is very interesting to see the best and fastest solutions. The speed is incredible ... but, like in my last comment to BlacKow I have compared your and my result: imgur.com/L2gNv9h . Do you know from where the difference comes from?. Are you calculating the mean of msd = Mean[dx^2] + Mean[dy^2] ? – mrz Apr 8 '16 at 15:08
• I would be very interested if you can reproduce the data I got (see my question above): msdMean, msdStdDev, xSquaredMean, xSquaredStdDev, ySquaredMean, ySquaredStdDev. I got from the developers from trackpy some info, which hopefully helps you: 1. the MSD should be done by looking at non-overlapping windows of a given time and then averaging those. There was some recent work (github.com/soft-matter/trackpy/pull/337) to make msd computations faster. 2. See github.com/soft-matter/trackpy/pull/352 for discussion of computing errors on the msd. – mrz Apr 12 '16 at 10:02
• I started a bounty and would be happy if you would have time to look again in your fft solution. I am very much interested that the numerical results of my code can be calculated/reproduced for the whole set of calculations I did (three mean value data sets and their errors). I cannot believe that any other code can be faster than yours. But it is important that we get the same numerical output. – mrz Apr 12 '16 at 10:09
• @mrz. See my update. Check it against yours to make sure it's correct. – RunnyKine Apr 13 '16 at 8:10
• Wonderful ... the same results now. Is it possible to show how you would combine the calculations of all the data sets msdMean, msdStdDev, xSquaredMean, xSquaredStdDev, ySquaredMean, ySquaredStdDev (as shown in my question)? I would like to compare the performance of your full solution with what BlacKow showed (may be also for larger data sets). Nevertheless I will later ask you and BlacKow if you allow to upload you codes to github. There are until now no codes for the MSD available which are programed with mathematica. That is very important for Physics and Chemistry. – mrz Apr 16 '16 at 12:34