A fast algorithm for 3D azimuthally anisotropic velocity scan

Next: Numerical examples Up: Theory Previous: Basic formulation

## Fast 3D butterfly algorithm

Equation 10 is the discretized form of a 3D oscillatory integral of the type

 (11)

whose fast evaluation can be realized by a butterfly algorithm (Candès et al., 2009).

The overall structure of the 3D butterfly algorithm basically follows its 2D analogue. The idea is to partition the computational domains and recursively into a pair of octrees, and , ending at level (see Figure 1 for an illustration). Here is chosen as an integer power of two, which is on the order of the maximum of for all possible and (so it is mainly determined by the range of variables and ). A crucial property of this structure is that at arbitrary level , the side lengths of a box in and of a box in always satisfy . Then when , restricted in and respectively, one can construct a low-rank, separated expansion for the kernel function (via a Chebyshev interpolation):

 (12)

By embedding this approximation in the above tree structure and traversing from top to bottom, from bottom to top, we arrive at a fast algorithm running in complexity (there are pairs of boxes on every level, and there are levels in total). Detailed description of the algorithm can be found in Hu et al. (2013), where the difference between 2D and 3D formulations should be clear from the context.

cube
Figure 1.
Butterfly tree structure for the special case of .

Considering the initial Fourier transform for preparing data in domain, the overall complexity of our algorithm is roughly ( terms are due to low-rank approximations, and is bigger than ).

By comparison, the conventional straightforward velocity scan requires at least computations, which may quickly become a bottleneck as the problem size increases. Yet the efficiency of our algorithm is controlled mainly by with an -dependent constant, where is determined by the degree of oscillations in the kernel . Generally speaking, depends on the maximum frequency and offset in the dataset, and the range of parameters in the model space. In practice, can often be chosen smaller than the grid size.

The significance of above analysis for the fast algorithm lies in the fact that the input and output data sizes and have little impact on the final computational cost; a dense sampling therefore becomes affordable.

 A fast algorithm for 3D azimuthally anisotropic velocity scan

Next: Numerical examples Up: Theory Previous: Basic formulation

2015-03-27