Non-reproducible behaviors in computing amidst different runs can involve several mechanisms, sometimes mixed. They can be especially sensitive when one iterates calculations on large sets of data, like inverse 3D tomography.
- soft errors, caused by defects, interaction with high-energy particles in spacecrafts (let's rule them out for now)
- number representations, different systems and OSes and not sufficiently specified rules for floats like rounding, overflow,
- code and compiler options: sometimes
x=a+b differs from
- hardware management, especially related to forms of parallelization on heterogeneous collections of processors (CPU, GPU): sometimes,
x=a+b+c+d does not give the same results when computed (on two units) either as
The non-deterministic aspect might arise, mostly, from the fourth type, as from one run to the other, a different set, or a different grouping can be performed.
[EDIT] Specifically to FFTW3, the documentation says:
Question 3.8. FFTW gives different results between runs
If you use FFTW_MEASURE or FFTW_PATIENT mode, then the algorithm FFTW
employs is not deterministic: it depends on runtime performance
measurements. This will cause the results to vary slightly from run to
run. However, the differences should be slight, on the order of the
floating-point precision, and therefore should have no practical
impact on most applications. If you use saved plans (wisdom) or
FFTW_ESTIMATE mode, however, then the algorithm is deterministic and
the results should be identical between runs.
It is for instance discussed in Not So Fast - The Hacker Factor Blog
Some of the shortcuts are very fast but are non-deterministic
This could be checked in you case.
A few quick sources: