A fast butterfly algorithm for generalized Radon transforms

Next: Bibliography Up: A fast butterfly algorithm Previous: Conclusions

# Acknowledgments

We are grateful to Tariq Alkhalifah, Anatoly Baumstein, Ian Moore, Daniel Trad, and the anonymous reviewer for their valuable comments and suggestions. We thank Dr. Alexander Klokov for preprocessing the field data. We thank KAUST and sponsors of the Texas Consortium for Computational Seismology (TCCS) for financial support.

# The mathematical derivation of the fast butterfly algorithm

This appendix gives a complete derivation and description of the butterfly algorithm, which combines the low-rank approximations and the butterfly structure introduced in the main text. For more mathematical exposition, the reader is referred to Candès et al. (2009).

To facilitate the presentation, we add a new figure (Figure A-1) to illustrate the notations.

1. Initialization. At level , let be the root box of . For each leaf box , expressions 9 and 10 are valid as . Substituting (in equation 10) into the definition of , equation 21, we get

 (32)

i.e. the equation 23 in the main text. In addition, for , the partial sum in equation 20 is given by (with (in equation 9) plugged in)

 (33)

Comparing the right hand sides of equations 19 and A-2, if we call the sources at , then coefficients are just like the equivalent sources at . This initial step is to redistribute the original sources located at (denoted by blue dots in Figure A-1) to equivalent sources located at Chebyshev grid (not shown in the figure). We next aim at updating until the end level .

2. Recursion. At , for each pair , let be 's parent and be 's children from the previous level (see Figure A-1). For each child , we have available from the previous level an approximation of the form

 for (34)

Summing over all children gives

 for (35)

Since , this is of course true for any . Also we know that equation 17 holds for , i.e.,

 for (36)

Inserting it into expression A-4 yields

 for (37)

On the other hand, admits a low-rank approximation of equivalent sources at the current level,

 for (38)

Equating expressions A-6 and A-7 suggests that we can take

 (39)

Substituting (in equation 10), we get

 (40)

i.e. the equation 24 in the main text.

3. Switch. A switch of the representation to expressions 11 and 12 is needed at the middle level since expressions 9 and 10 are no longer valid as soon as (boxes are getting bigger and bigger so that is no longer satisfied). Plugging (in equation 12) into the definition of , equation 21, one has

 (41)

from expression A-7,

 (42)

where we use to denote the new set of coefficients and the old set. Equating expressions A-10 and A-11, we can set as

 (43)

i.e. the equation 25 in the main text. This middle step is to switch from equivalent sources located at Chebyshev grid on the side to equivalent sources located at Chebyshev grid on the side.

4. Recursion. The rest of the recursion is analogous to Step 2. For , we have

 for (44)

thus

 (45)

recalling expression A-10, one can simply set

 (46)

Inserting (in equation 11) gives the update

 (47)

i.e. the equation 26 in the main text.

5. Termination. Finally we reach the level , and is the entire domain . For every box in and every ,

 (48)

Plugging in (in equation 11), we get

 (49)

i.e. the equation 27 in the main text. This final step is to transform the equivalent sources located at Chebyshev grid back to the targets located at (denoted by red dots in Figure A-1).

In the above algorithm, is assumed to be an even number. If is odd, one can either switch at level or . Everything else remains unchanged.

illus
Figure A-1.
The butterfly structure for the special case of . The top right panel represents the input domain with sources located at (blue dots). The bottom left panel represents the output domain with targets located at (red dots). For the pair of boxes at level , box is called 's parent at the previous level; four small boxes are called 's children at the previous level.

 A fast butterfly algorithm for generalized Radon transforms

Next: Bibliography Up: A fast butterfly algorithm Previous: Conclusions

2013-07-26