![]() |
![]() |
![]() |
![]() | A fast algorithm for 3D azimuthally anisotropic velocity scan | ![]() |
![]() |
Equation 10 is the discretized form of a 3D oscillatory integral of the type
![]() |
(11) |
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):
![]() |
---|
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 | ![]() |
![]() |