  We introduce two efficient algorithms for computing the partial
  Fourier transforms in one and two dimensions. Our study is motivated by the
wave extrapolation procedure in reflection seismology. In both algorithms, the
main idea is to decompose the summation domain of into simpler components in a
multiscale way. Existing fast algorithms are then applied to each component to
obtain optimal complexity. The algorithm in 1D is exact and takes $O(N\log^2
N)$ steps. Our solution in 2D is an approximate but accurate algorithm that
takes $O(N^2 \log^2 N)$ steps. In both cases, the complexities are almost
linear in terms of the degree of freedom. We provide numerical results on
several test examples.
