A fast butterfly algorithm for generalized Radon transforms

Numerical examples

In this section we provide several numerical examples to illustrate the empirical properties of the fast butterfly algorithm. To check the results qualitatively, we compare with the velocity scan method (the nearest neighbor interpolation is used to minimize the interpolation cost); to test the results quantitatively, however, it makes more sense to compare with the direct evaluation of equation 3, since the fast algorithm is to speed up this summation in the frequency domain, whereas the velocity scan computes a slightly different sum in the time domain, which may contain interpolation artifacts.

There is no general rule for selecting parameters $N$ , $q_{k_1}$ , $q_{k_2}$ , ... The larger $N$ is, the fewer Chebyshev points are needed, and vice versa. In practice, parameters can be tuned to achieve the best efficiency and accuracy trade-off. For simplicity, in the following examples $N$ and $q_{k_1}$ , $q_{k_2}$ , $q_{x_1}$ , $q_{x_2}$ are chosen such that the relative error between the fast algorithm and the direct computation of equation 3 is about $O(10^{-2})$ . These combinations are not necessarily optimal in terms of efficiency.

A fast butterfly algorithm for generalized Radon transforms