A fast butterfly algorithm for generalized Radon transforms

Published as Geophysics, 78, no. 4, U41-U51, (2013)

A fast butterfly algorithm for generalized Radon transforms

Jingwei Hu, Sergey Fomel, Laurent Demanet, and Lexing Ying
Institute for Computational Engineering and Sciences (ICES)
The University of Texas at Austin
201 East 24th St, Stop C0200, Austin, TX 78712, USA
hu@ices.utexas.edu
Bureau of Economic Geology and Department of Geological Sciences
Jackson School of Geosciences
The University of Texas at Austin
University Station, Box X, Austin, TX 78713, USA
sergey.fomel@beg.utexas.edu
Department of Mathematics
Massachusetts Institute of Technology
77 Massachusetts Avenue, Cambridge, MA 02139, USA
laurent@math.mit.edu
Department of Mathematics and
Institute for Computational and Mathematical Engineering (ICME)
Stanford University
450 Serra Mall, Bldg 380, Stanford, CA 94305, USA
lexing@math.stanford.edu

Abstract:

Generalized Radon transforms such as the hyperbolic Radon transform cannot be implemented as efficiently in the frequency domain as convolutions, thus limiting their use in seismic data processing. We introduce a fast butterfly algorithm for the hyperbolic Radon transform. The basic idea is to reformulate the transform as an oscillatory integral operator and to construct a blockwise low-rank approximation of the kernel function. The overall structure follows the Fourier integral operator (FIO) butterfly algorithm. For two-dimensional data, the algorithm runs in complexity $O(N^2\log N)$ , where $N$ depends on the maximum frequency and offset in the dataset and the range of parameters (intercept time and slowness) in the model space. Using a series of examples, we show that the proposed algorithm can be significantly more efficient than the conventional time-domain integration.

A fast butterfly algorithm for generalized Radon transforms