Home People Software Projects Alumni Links

Nonstandard Fourier Methods


A major recent initiative in our group concerns nonstandard numerical applications of Fourier analysis. An essential algorithm in this context is the non-uniform fast Fourier transform (NUFFT). In a typical problem, one is given an irregular sampling of N points in the frequency domain and is interested in rapidly reconstructing the corresponding function at N points in the physical domain. The NUFFT carries out this computation in O(N log N) operations.

Magnetic Resonance Imaging

In magnetic resonance imaging, we have shown that the NUFFT together with a new approach to quadrature in the Fourier domain leads to fast and accurate image reconstruction using the kinds of experimental data acquired in "fast" imaging modalities

  • L. Greengard, J.-Y. Lee, and S. Inati, The Fast Sinc Transform and Image Reconstruction from Non-uniform Samples in k-space, Comm. Appl. Math. and Comp. Sci. 1, 121-132 (2006).
  • Application to Heat Flow

    We have developed a fast solver for the inhomogeneous heat equation in unbounded domains. While the most commonly used approaches are based on finite difference and finite element methods, these must be coupled to artificial (non-reflecting) boundary conditions imposed on a finite computational domain in order to simulate the effect of diffusion into an infinite medium. Our approach, which we refer to as the Fast Recursive Marching (FRM) method, is mathematically much more straightforward. The FRM method is based on evaluating the exact solution of the governing equation, using convolution with the free-space Green's function to compute a volume integral in space-time. This is carried out in the Fourier domain and relies on the spectral approximation of the free-space heat kernel

  • L. Greengard and P. Lin Spectral Approximation of the Free-Space Heat Kernel ,  Appl. Comput. Harmonic Anal. 9, 83-97 (2000).
  • coupled with the NUFFT. There are several advantages to this approach. The FRM method is explicit, unconditionally stable, and requires an amount of work of the order O(NM log N) where N is the number of discretization points in physical space and M is the number of time steps

  • J.-R. Li and L. Greengard, On the Numerical Solution of the Heat Equation I: Fast solvers in free space ,  J. Comput. Phys. 226, 1891--1901 (2007).
  • We have also developed NUFFT-based schemes for the rapid evaluation of heat potentials in complex geometry

  • J.-R. Li and L. Greengard, High Order Accurate Methods for the Evaluation of Layer Heat Potentials , SIAM J. Sci. Comput. 31 , 3847-3860 (2009)
  • Our goal is to develop a core set of tools that will enable the creation of a new generation of unconditionally stable, explicit solvers for the heat equation in complex geometry. This is not possible with classical methods, but is made feasible by adopting an integral-equation viewpoint. The price to pay is a more intricate set of core library components.

    Technical references:

  • L. Greengard and J. Strain, A Fast Algorithm for the Evaluation of Heat Potentials ,   published version: Comm. Pure Appl. Math. 43, 949-963 (1990).
  • L. Greengard and J. Strain, The Fast Gauss Transform
    ,   SIAM J. Sci. Stat. Comput. 12, 79 (1991).