  The nonlinear Fourier transform, which is also known as the forward
scattering transform, decomposes a periodic signal into nonlinearly interacting
waves. In contrast to the common Fourier transform, these waves no longer have
to be sinusoidal. Physically relevant waveforms are often available for the
analysis instead. The details of the transform depend on the waveforms
underlying the analysis, which in turn are specified through the implicit
assumption that the signal is governed by a certain evolution equation. For
example, water waves generated by the Korteweg-de Vries equation can be
expressed in terms of cnoidal waves. Light waves in optical fiber governed by
the nonlinear Schr\"odinger equation (NSE) are another example. Nonlinear
analogs of classic problems such as spectral analysis and filtering arise in
many applications, with information transmission in optical fiber, as proposed
by Yousefi and Kschischang, being a very recent one. The nonlinear Fourier
transform is eminently suited to address them -- at least from a theoretical
point of view. Although numerical algorithms are available for computing the
transform, a "fast" nonlinear Fourier transform that is similarly effective as
the fast Fourier transform is for computing the common Fourier transform has
not been available so far. The goal of this paper is to address this problem.
Two fast numerical methods for computing the nonlinear Fourier transform with
respect to the NSE are presented. The first method achieves a runtime of
$O(D^2)$ floating point operations, where $D$ is the number of sample points.
The second method applies only to the case where the NSE is defocusing, but it
achieves an $O(D\log^2D)$ runtime. Extensions of the results to other evolution
equations are discussed as well.
