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

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.

Figure 1

11/16/1997