# 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).