Both the slow Fourier transform (SFT) and interpolation algorithms have been implemented on the CM5 and their running times compared. The SFT involves a matrix multiplication and therefore is an algorithm in . However, a parallel machine with P processors will perform these computations in a time proportional to with some additional but smaller communication cost.
The serial implementation of the interpolation filter requires a number of computations proportional to , where m is the length of the filters. For large values of N, the interpolation algorithm will prove more efficient than the SFT algorithm. However, because the SFT algorithm runs P times faster on a parallel machine whereas the interpolation algorithm does not improve its speed, what was considered a large number N appears now as a smaller number. Indeed, for a trace length of 2048, the SFT algorithm runs four times as fast as the other:
SFT: 111.7 real 100.2 user 0.7 sys Interpolation: 489.0 real 471.8 user 4.5 sysMoreover, as the trace length decreases, the running time ratio increases in such a way that, for 1024 time samples (a usual trace length), it becomes one to eight:
SFT: 99.7 real 30.0 user 1.7 sys Interpolation: 447.8 real 241.0 user 6.0 sysThe user times are more significant than the real times which depend a lot on the current load of the machine.
The slow Fourier transform algorithm proves efficient not only for its speed but also for the artifact-free migration that it produces. Figure illustrates this point.