Merge from the doc wiki

1 files changed, 163 insertions, 20 deletions

diff --git a/numpy/fft/info.py b/numpy/fft/info.py
index c9ab599a4..77630e92b 100644
--- a/numpy/fft/info.py
+++ b/numpy/fft/info.py
@@ -1,29 +1,172 @@
-"""\
-Core FFT routines
-==================
+"""
+Discrete Fourier Transform (:mod:`numpy.fft`)
+=============================================
+
+.. currentmodule:: numpy.fft
+
+
+Standard FFTs
+-------------
+
+.. autosummary::
+   :toctree: generated/
+
+   fft       Discrete Fourier transform.
+   ifft      Inverse discrete Fourier transform.
+   fft2      Discrete Fourier transform in two dimensions.
+   ifft2     Inverse discrete Fourier transform in two dimensions.
+   fftn      Discrete Fourier transform in N-dimensions.
+   ifftn     Inverse discrete Fourier transform in N dimensions.
+
+Real FFTs
+---------
+
+.. autosummary::
+   :toctree: generated/
+
+   rfft      Real discrete Fourier transform.
+   irfft     Inverse real discrete Fourier transform.
+   rfft2     Real discrete Fourier transform in two dimensions.
+   irfft2    Inverse real discrete Fourier transform in two dimensions.
+   rfftn     Real discrete Fourier transform in N dimensions.
+   irfftn    Inverse real discrete Fourier transform in N dimensions.
+
+
+Hermitian FFTs
+--------------
+
+.. autosummary::
+   :toctree: generated/
+
+   hfft      Hermitian discrete Fourier transform.
+   ihfft     Inverse Hermitian discrete Fourier transform.
+
+
+Helper routines
+---------------
+
+.. autosummary::
+   :toctree: generated/
+
+   fftfreq   Discrete Fourier Transform sample frequencies.
+   fftshift  Shift zero-frequency component to center of spectrum.
+   ifftshift Inverse of fftshift.
+
+Background information
+----------------------
+
+Fourier analysis is fundamentally a method for expressing a function as a
+sum of periodic components, and for recovering the signal from those
+components.  When both the function and its Fourier transform are
+replaced with discretized counterparts, it is called the discrete Fourier
+transform (DFT).  The DFT has become a mainstay of numerical computing in
+part because of a very fast algorithm for computing it, called the Fast
+Fourier Transform (FFT), which was known to Gauss (1805) and was brought
+to light in its current form by Cooley and Tukey [CT]_.  Press et al. [NR]_
+provide an accessible introduction to Fourier analysis and its
+applications.
+
+Because the discrete Fourier transform separates its input into
+components that contribute at discrete frequencies, it has a great number
+of applications in digital signal processing, e.g., for filtering, and in
+this context the discretized input to the transform is customarily
+referred to as a *signal*, which exists in the *time domain*.  The output
+is called a *spectrum* or *transform* and exists in the *frequency
+domain*.
+
+There are many ways to define the DFT, varying in the sign of the
+exponent, normalization, etc.  In this implementation, the DFT is defined
+as
+
+.. math::
+   A_k =  \\sum_{m=0}^{n-1} a_m \\exp\\left\\{-2\\pi i{mk \\over n}\\right\\}
+   \\qquad k = 0,\\ldots,n-1.
+
+The DFT is in general defined for complex inputs and outputs, and a
+single-frequency component at linear frequency :math:`f` is
+represented by a complex exponential
+:math:`a_m = \\exp\\{2\\pi i\\,f m\\Delta t\\}`, where :math:`\\Delta t`
+is the sampling interval.
+
+The values in the result follow so-called "standard" order: If `A =
+fft(a, n)`, then `A[0]` contains the zero-frequency term (the mean of the
+signal), which is always purely real for real inputs. Then `A[1:n/2]`
+contains the positive-frequency terms, and `A[n/2+1:]` contains the
+negative-frequency terms, in order of decreasingly negative frequency.
+For an even number of input points, `A[n/2]` represents both positive and
+negative Nyquist frequency, and is also purely real for real input.  For
+an odd number of input points, `A[(n-1)/2]` contains the largest positive
+frequency, while `A[(n+1)/2]` contains the largest negative frequency.
+The routine `np.fft.fftfreq(A)` returns an array giving the frequencies
+of corresponding elements in the output.  The routine
+`np.fft.fftshift(A)` shifts transforms and their frequencies to put the
+zero-frequency components in the middle, and `np.fft.ifftshift(A)` undoes
+that shift.
+
+When the input `a` is a time-domain signal and `A = fft(a)`, `np.abs(A)`
+is its amplitude spectrum and `np.abs(A)**2` is its power spectrum.
+The phase spectrum is obtained by `np.angle(A)`.
+
+The inverse DFT is defined as
+
+.. math::
+   a_m = \\frac{1}{n}\\sum_{k=0}^{n-1}A_k\\exp\\left\\{2\\pi i{mk\\over n}\\right\\}
+   \\qquad n = 0,\\ldots,n-1.
+
+It differs from the forward transform by the sign of the exponential
+argument and the normalization by :math:`1/n`.
+
+Real and Hermitian transforms
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+When the input is purely real, its transform is Hermitian, i.e., the
+component at frequency :math:`f_k` is the complex conjugate of the
+component at frequency :math:`-f_k`, which means that for real
+inputs there is no information in the negative frequency components that
+is not already available from the positive frequency components.
+The family of `rfft` functions is
+designed to operate on real inputs, and exploits this symmetry by
+computing only the positive frequency components, up to and including the
+Nyquist frequency.  Thus, `n` input points produce `n/2+1` complex
+output points.  The inverses of this family assumes the same symmetry of
+its input, and for an output of `n` points uses `n/2+1` input points.
+
+Correspondingly, when the spectrum is purely real, the signal is
+Hermitian.  The `hfft` family of functions exploits this symmetry by
+using `n/2+1` complex points in the input (time) domain for `n` real
+points in the frequency domain.
+
+In higher dimensions, FFTs are used, e.g., for image analysis and
+filtering.  The computational efficiency of the FFT means that it can
+also be a faster way to compute large convolutions, using the property
+that a convolution in the time domain is equivalent to a point-by-point
+multiplication in the frequency domain.
+
+In two dimensions, the DFT is defined as
+
+.. math::
+   A_{kl} =  \\sum_{m=0}^{M-1} \\sum_{n=0}^{N-1}
+   a_{mn}\\exp\\left\\{-2\\pi i \\left({mk\\over M}+{nl\\over N}\\right)\\right\\}
+   \\qquad k = 0, \\ldots, N-1;\\quad l = 0, \\ldots, M-1,
 
- Standard FFTs
+which extends in the obvious way to higher dimensions, and the inverses
+in higher dimensions also extend in the same way.
 
-   fft
-   ifft
-   fft2
-   ifft2
-   fftn
-   ifftn
+References
+^^^^^^^^^^
+.. [CT] Cooley, James W., and John W. Tukey, 1965, "An algorithm for the
+        machine calculation of complex Fourier series," *Math. Comput.*
+        19: 297-301.
 
- Real FFTs
+.. [NR] Press, W., Teukolsky, S., Vetterline, W.T., and Flannery, B.P.,
+        2007, *Numerical Recipes: The Art of Scientific Computing*, ch.
+        12-13.  Cambridge Univ. Press, Cambridge, UK.
 
-   rfft
-   irfft
-   rfft2
-   irfft2
-   rfftn
-   irfftn
+Examples
+^^^^^^^^
 
- Hermite FFTs
+For examples, see the various functions.
 
-   hfft
-   ihfft
 """
 
 depends = ['core']