diff options
author | Oscar Villellas <oscar.villellas@continuum.io> | 2017-01-03 20:28:00 +0100 |
---|---|---|
committer | Oscar Villellas <oscar.villellas@continuum.io> | 2017-01-03 20:28:00 +0100 |
commit | 4c93e28685eecfd359f7ca9ad6f8003f054626ca (patch) | |
tree | 91b81599f615d45e7103d55daf69b25d19eabe4a /numpy/fft/fftpack.py | |
parent | f555826ac776e0866e1edfc1804c88c2a23dab3b (diff) | |
parent | 02e2ea815a6c76152096364edd10e2dd954bcb56 (diff) | |
download | numpy-4c93e28685eecfd359f7ca9ad6f8003f054626ca.tar.gz |
Merge remote-tracking branch 'numpy-org/master' into mult-norm
Diffstat (limited to 'numpy/fft/fftpack.py')
-rw-r--r-- | numpy/fft/fftpack.py | 303 |
1 files changed, 201 insertions, 102 deletions
diff --git a/numpy/fft/fftpack.py b/numpy/fft/fftpack.py index 4efb2a9a0..7486ff51e 100644 --- a/numpy/fft/fftpack.py +++ b/numpy/fft/fftpack.py @@ -35,12 +35,14 @@ from __future__ import division, absolute_import, print_function __all__ = ['fft', 'ifft', 'rfft', 'irfft', 'hfft', 'ihfft', 'rfftn', 'irfftn', 'rfft2', 'irfft2', 'fft2', 'ifft2', 'fftn', 'ifftn'] -from numpy.core import asarray, zeros, swapaxes, shape, conjugate, \ - take +from numpy.core import (array, asarray, zeros, swapaxes, shape, conjugate, + take, sqrt) from . import fftpack_lite as fftpack +from .helper import _FFTCache + +_fft_cache = _FFTCache(max_size_in_mb=100, max_item_count=32) +_real_fft_cache = _FFTCache(max_size_in_mb=100, max_item_count=32) -_fft_cache = {} -_real_fft_cache = {} def _raw_fft(a, n=None, axis=-1, init_function=fftpack.cffti, work_function=fftpack.cfftf, fft_cache=_fft_cache): @@ -50,14 +52,16 @@ def _raw_fft(a, n=None, axis=-1, init_function=fftpack.cffti, n = a.shape[axis] if n < 1: - raise ValueError("Invalid number of FFT data points (%d) specified." % n) - - try: - # Thread-safety note: We rely on list.pop() here to atomically - # retrieve-and-remove a wsave from the cache. This ensures that no - # other thread can get the same wsave while we're using it. - wsave = fft_cache.setdefault(n, []).pop() - except (IndexError): + raise ValueError("Invalid number of FFT data points (%d) specified." + % n) + + # We have to ensure that only a single thread can access a wsave array + # at any given time. Thus we remove it from the cache and insert it + # again after it has been used. Multiple threads might create multiple + # copies of the wsave array. This is intentional and a limitation of + # the current C code. + wsave = fft_cache.pop_twiddle_factors(n) + if wsave is None: wsave = init_function(n) if a.shape[axis] != n: @@ -83,12 +87,19 @@ def _raw_fft(a, n=None, axis=-1, init_function=fftpack.cffti, # As soon as we put wsave back into the cache, another thread could pick it # up and start using it, so we must not do this until after we're # completely done using it ourselves. - fft_cache[n].append(wsave) + fft_cache.put_twiddle_factors(n, wsave) return r -def fft(a, n=None, axis=-1): +def _unitary(norm): + if norm not in (None, "ortho"): + raise ValueError("Invalid norm value %s, should be None or \"ortho\"." + % norm) + return norm is not None + + +def fft(a, n=None, axis=-1, norm=None): """ Compute the one-dimensional discrete Fourier Transform. @@ -108,6 +119,10 @@ def fft(a, n=None, axis=-1): axis : int, optional Axis over which to compute the FFT. If not given, the last axis is used. + norm : {None, "ortho"}, optional + .. versionadded:: 1.10.0 + + Normalization mode (see `numpy.fft`). Default is None. Returns ------- @@ -157,6 +172,10 @@ def fft(a, n=None, axis=-1): 1.14383329e-17 +1.22460635e-16j, -1.64863782e-15 +1.77635684e-15j]) + In this example, real input has an FFT which is Hermitian, i.e., symmetric + in the real part and anti-symmetric in the imaginary part, as described in + the `numpy.fft` documentation: + >>> import matplotlib.pyplot as plt >>> t = np.arange(256) >>> sp = np.fft.fft(np.sin(t)) @@ -165,16 +184,18 @@ def fft(a, n=None, axis=-1): [<matplotlib.lines.Line2D object at 0x...>, <matplotlib.lines.Line2D object at 0x...>] >>> plt.show() - In this example, real input has an FFT which is Hermitian, i.e., symmetric - in the real part and anti-symmetric in the imaginary part, as described in - the `numpy.fft` documentation. - """ - return _raw_fft(a, n, axis, fftpack.cffti, fftpack.cfftf, _fft_cache) + a = asarray(a).astype(complex, copy=False) + if n is None: + n = a.shape[axis] + output = _raw_fft(a, n, axis, fftpack.cffti, fftpack.cfftf, _fft_cache) + if _unitary(norm): + output *= 1 / sqrt(n) + return output -def ifft(a, n=None, axis=-1): +def ifft(a, n=None, axis=-1, norm=None): """ Compute the one-dimensional inverse discrete Fourier Transform. @@ -185,10 +206,16 @@ def ifft(a, n=None, axis=-1): see `numpy.fft`. The input should be ordered in the same way as is returned by `fft`, - i.e., ``a[0]`` should contain the zero frequency term, - ``a[1:n/2+1]`` should contain the positive-frequency terms, and - ``a[n/2+1:]`` should contain the negative-frequency terms, in order of - decreasingly negative frequency. See `numpy.fft` for details. + i.e., + + * ``a[0]`` should contain the zero frequency term, + * ``a[1:n//2]`` should contain the positive-frequency terms, + * ``a[n//2 + 1:]`` should contain the negative-frequency terms, in + increasing order starting from the most negative frequency. + + For an even number of input points, ``A[n//2]`` represents the sum of + the values at the positive and negative Nyquist frequencies, as the two + are aliased together. See `numpy.fft` for details. Parameters ---------- @@ -203,6 +230,10 @@ def ifft(a, n=None, axis=-1): axis : int, optional Axis over which to compute the inverse DFT. If not given, the last axis is used. + norm : {None, "ortho"}, optional + .. versionadded:: 1.10.0 + + Normalization mode (see `numpy.fft`). Default is None. Returns ------- @@ -242,20 +273,22 @@ def ifft(a, n=None, axis=-1): >>> n[40:60] = np.exp(1j*np.random.uniform(0, 2*np.pi, (20,))) >>> s = np.fft.ifft(n) >>> plt.plot(t, s.real, 'b-', t, s.imag, 'r--') - [<matplotlib.lines.Line2D object at 0x...>, <matplotlib.lines.Line2D object at 0x...>] + ... >>> plt.legend(('real', 'imaginary')) - <matplotlib.legend.Legend object at 0x...> + ... >>> plt.show() """ - - a = asarray(a).astype(complex) + # The copy may be required for multithreading. + a = array(a, copy=True, dtype=complex) if n is None: - n = shape(a)[axis] - return _raw_fft(a, n, axis, fftpack.cffti, fftpack.cfftb, _fft_cache) / n + n = a.shape[axis] + unitary = _unitary(norm) + output = _raw_fft(a, n, axis, fftpack.cffti, fftpack.cfftb, _fft_cache) + return output * (1 / (sqrt(n) if unitary else n)) -def rfft(a, n=None, axis=-1): +def rfft(a, n=None, axis=-1, norm=None): """ Compute the one-dimensional discrete Fourier Transform for real input. @@ -275,6 +308,10 @@ def rfft(a, n=None, axis=-1): axis : int, optional Axis over which to compute the FFT. If not given, the last axis is used. + norm : {None, "ortho"}, optional + .. versionadded:: 1.10.0 + + Normalization mode (see `numpy.fft`). Default is None. Returns ------- @@ -329,12 +366,16 @@ def rfft(a, n=None, axis=-1): exploited to compute only the non-negative frequency terms. """ + # The copy may be required for multithreading. + a = array(a, copy=True, dtype=float) + output = _raw_fft(a, n, axis, fftpack.rffti, fftpack.rfftf, + _real_fft_cache) + if _unitary(norm): + output *= 1 / sqrt(a.shape[axis]) + return output - a = asarray(a).astype(float) - return _raw_fft(a, n, axis, fftpack.rffti, fftpack.rfftf, _real_fft_cache) - -def irfft(a, n=None, axis=-1): +def irfft(a, n=None, axis=-1, norm=None): """ Compute the inverse of the n-point DFT for real input. @@ -362,6 +403,10 @@ def irfft(a, n=None, axis=-1): axis : int, optional Axis over which to compute the inverse FFT. If not given, the last axis is used. + norm : {None, "ortho"}, optional + .. versionadded:: 1.10.0 + + Normalization mode (see `numpy.fft`). Default is None. Returns ------- @@ -410,31 +455,38 @@ def irfft(a, n=None, axis=-1): specified, and the output array is purely real. """ - - a = asarray(a).astype(complex) + # The copy may be required for multithreading. + a = array(a, copy=True, dtype=complex) if n is None: - n = (shape(a)[axis] - 1) * 2 - return _raw_fft(a, n, axis, fftpack.rffti, fftpack.rfftb, - _real_fft_cache) / n + n = (a.shape[axis] - 1) * 2 + unitary = _unitary(norm) + output = _raw_fft(a, n, axis, fftpack.rffti, fftpack.rfftb, + _real_fft_cache) + return output * (1 / (sqrt(n) if unitary else n)) -def hfft(a, n=None, axis=-1): +def hfft(a, n=None, axis=-1, norm=None): """ - Compute the FFT of a signal which has Hermitian symmetry (real spectrum). + Compute the FFT of a signal that has Hermitian symmetry, i.e., a real + spectrum. Parameters ---------- a : array_like The input array. n : int, optional - Length of the transformed axis of the output. - For `n` output points, ``n//2+1`` input points are necessary. If the - input is longer than this, it is cropped. If it is shorter than this, - it is padded with zeros. If `n` is not given, it is determined from - the length of the input along the axis specified by `axis`. + Length of the transformed axis of the output. For `n` output + points, ``n//2 + 1`` input points are necessary. If the input is + longer than this, it is cropped. If it is shorter than this, it is + padded with zeros. If `n` is not given, it is determined from the + length of the input along the axis specified by `axis`. axis : int, optional Axis over which to compute the FFT. If not given, the last axis is used. + norm : {None, "ortho"}, optional + Normalization mode (see `numpy.fft`). Default is None. + + .. versionadded:: 1.10.0 Returns ------- @@ -442,8 +494,9 @@ def hfft(a, n=None, axis=-1): The truncated or zero-padded input, transformed along the axis indicated by `axis`, or the last one if `axis` is not specified. The length of the transformed axis is `n`, or, if `n` is not given, - ``2*(m-1)`` where ``m`` is the length of the transformed axis of the - input. To get an odd number of output points, `n` must be specified. + ``2*m - 2`` where ``m`` is the length of the transformed axis of + the input. To get an odd number of output points, `n` must be + specified, for instance as ``2*m - 1`` in the typical case, Raises ------ @@ -458,10 +511,12 @@ def hfft(a, n=None, axis=-1): Notes ----- `hfft`/`ihfft` are a pair analogous to `rfft`/`irfft`, but for the - opposite case: here the signal has Hermitian symmetry in the time domain - and is real in the frequency domain. So here it's `hfft` for which - you must supply the length of the result if it is to be odd: - ``ihfft(hfft(a), len(a)) == a``, within numerical accuracy. + opposite case: here the signal has Hermitian symmetry in the time + domain and is real in the frequency domain. So here it's `hfft` for + which you must supply the length of the result if it is to be odd. + + * even: ``ihfft(hfft(a, 2*len(a) - 2) == a``, within roundoff error, + * odd: ``ihfft(hfft(a, 2*len(a) - 1) == a``, within roundoff error. Examples -------- @@ -484,38 +539,42 @@ def hfft(a, n=None, axis=-1): [ 2., -2.]]) """ - - a = asarray(a).astype(complex) + # The copy may be required for multithreading. + a = array(a, copy=True, dtype=complex) if n is None: - n = (shape(a)[axis] - 1) * 2 - return irfft(conjugate(a), n, axis) * n + n = (a.shape[axis] - 1) * 2 + unitary = _unitary(norm) + return irfft(conjugate(a), n, axis) * (sqrt(n) if unitary else n) -def ihfft(a, n=None, axis=-1): +def ihfft(a, n=None, axis=-1, norm=None): """ - Compute the inverse FFT of a signal which has Hermitian symmetry. + Compute the inverse FFT of a signal that has Hermitian symmetry. Parameters ---------- a : array_like Input array. n : int, optional - Length of the inverse FFT. - Number of points along transformation axis in the input to use. - If `n` is smaller than the length of the input, the input is cropped. - If it is larger, the input is padded with zeros. If `n` is not given, - the length of the input along the axis specified by `axis` is used. + Length of the inverse FFT, the number of points along + transformation axis in the input to use. If `n` is smaller than + the length of the input, the input is cropped. If it is larger, + the input is padded with zeros. If `n` is not given, the length of + the input along the axis specified by `axis` is used. axis : int, optional Axis over which to compute the inverse FFT. If not given, the last axis is used. + norm : {None, "ortho"}, optional + Normalization mode (see `numpy.fft`). Default is None. + + .. versionadded:: 1.10.0 Returns ------- out : complex ndarray The truncated or zero-padded input, transformed along the axis indicated by `axis`, or the last one if `axis` is not specified. - If `n` is even, the length of the transformed axis is ``(n/2)+1``. - If `n` is odd, the length is ``(n+1)/2``. + The length of the transformed axis is ``n//2 + 1``. See also -------- @@ -524,10 +583,12 @@ def ihfft(a, n=None, axis=-1): Notes ----- `hfft`/`ihfft` are a pair analogous to `rfft`/`irfft`, but for the - opposite case: here the signal has Hermitian symmetry in the time domain - and is real in the frequency domain. So here it's `hfft` for which - you must supply the length of the result if it is to be odd: - ``ihfft(hfft(a), len(a)) == a``, within numerical accuracy. + opposite case: here the signal has Hermitian symmetry in the time + domain and is real in the frequency domain. So here it's `hfft` for + which you must supply the length of the result if it is to be odd: + + * even: ``ihfft(hfft(a, 2*len(a) - 2) == a``, within roundoff error, + * odd: ``ihfft(hfft(a, 2*len(a) - 1) == a``, within roundoff error. Examples -------- @@ -538,11 +599,13 @@ def ihfft(a, n=None, axis=-1): array([ 1.-0.j, 2.-0.j, 3.-0.j, 4.-0.j]) """ - - a = asarray(a).astype(float) + # The copy may be required for multithreading. + a = array(a, copy=True, dtype=float) if n is None: - n = shape(a)[axis] - return conjugate(rfft(a, n, axis))/n + n = a.shape[axis] + unitary = _unitary(norm) + output = conjugate(rfft(a, n, axis)) + return output * (1 / (sqrt(n) if unitary else n)) def _cook_nd_args(a, s=None, axes=None, invreal=0): @@ -564,17 +627,17 @@ def _cook_nd_args(a, s=None, axes=None, invreal=0): return s, axes -def _raw_fftnd(a, s=None, axes=None, function=fft): +def _raw_fftnd(a, s=None, axes=None, function=fft, norm=None): a = asarray(a) s, axes = _cook_nd_args(a, s, axes) itl = list(range(len(axes))) itl.reverse() for ii in itl: - a = function(a, n=s[ii], axis=axes[ii]) + a = function(a, n=s[ii], axis=axes[ii], norm=norm) return a -def fftn(a, s=None, axes=None): +def fftn(a, s=None, axes=None, norm=None): """ Compute the N-dimensional discrete Fourier Transform. @@ -588,8 +651,8 @@ def fftn(a, s=None, axes=None): Input array, can be complex. s : sequence of ints, optional Shape (length of each transformed axis) of the output - (`s[0]` refers to axis 0, `s[1]` to axis 1, etc.). - This corresponds to `n` for `fft(x, n)`. + (``s[0]`` refers to axis 0, ``s[1]`` to axis 1, etc.). + This corresponds to ``n`` for ``fft(x, n)``. Along any axis, if the given shape is smaller than that of the input, the input is cropped. If it is larger, the input is padded with zeros. if `s` is not given, the shape of the input along the axes specified @@ -599,6 +662,10 @@ def fftn(a, s=None, axes=None): axes are used, or all axes if `s` is also not specified. Repeated indices in `axes` means that the transform over that axis is performed multiple times. + norm : {None, "ortho"}, optional + .. versionadded:: 1.10.0 + + Normalization mode (see `numpy.fft`). Default is None. Returns ------- @@ -664,9 +731,10 @@ def fftn(a, s=None, axes=None): """ - return _raw_fftnd(a, s, axes, fft) + return _raw_fftnd(a, s, axes, fft, norm) -def ifftn(a, s=None, axes=None): + +def ifftn(a, s=None, axes=None, norm=None): """ Compute the N-dimensional inverse discrete Fourier Transform. @@ -700,6 +768,10 @@ def ifftn(a, s=None, axes=None): axes are used, or all axes if `s` is also not specified. Repeated indices in `axes` means that the inverse transform over that axis is performed multiple times. + norm : {None, "ortho"}, optional + .. versionadded:: 1.10.0 + + Normalization mode (see `numpy.fft`). Default is None. Returns ------- @@ -756,10 +828,10 @@ def ifftn(a, s=None, axes=None): """ - return _raw_fftnd(a, s, axes, ifft) + return _raw_fftnd(a, s, axes, ifft, norm) -def fft2(a, s=None, axes=(-2, -1)): +def fft2(a, s=None, axes=(-2, -1), norm=None): """ Compute the 2-dimensional discrete Fourier Transform @@ -774,8 +846,8 @@ def fft2(a, s=None, axes=(-2, -1)): Input array, can be complex s : sequence of ints, optional Shape (length of each transformed axis) of the output - (`s[0]` refers to axis 0, `s[1]` to axis 1, etc.). - This corresponds to `n` for `fft(x, n)`. + (``s[0]`` refers to axis 0, ``s[1]`` to axis 1, etc.). + This corresponds to ``n`` for ``fft(x, n)``. Along each axis, if the given shape is smaller than that of the input, the input is cropped. If it is larger, the input is padded with zeros. if `s` is not given, the shape of the input along the axes specified @@ -785,6 +857,10 @@ def fft2(a, s=None, axes=(-2, -1)): axes are used. A repeated index in `axes` means the transform over that axis is performed multiple times. A one-element sequence means that a one-dimensional FFT is performed. + norm : {None, "ortho"}, optional + .. versionadded:: 1.10.0 + + Normalization mode (see `numpy.fft`). Default is None. Returns ------- @@ -842,10 +918,10 @@ def fft2(a, s=None, axes=(-2, -1)): """ - return _raw_fftnd(a, s, axes, fft) + return _raw_fftnd(a, s, axes, fft, norm) -def ifft2(a, s=None, axes=(-2, -1)): +def ifft2(a, s=None, axes=(-2, -1), norm=None): """ Compute the 2-dimensional inverse discrete Fourier Transform. @@ -878,6 +954,10 @@ def ifft2(a, s=None, axes=(-2, -1)): axes are used. A repeated index in `axes` means the transform over that axis is performed multiple times. A one-element sequence means that a one-dimensional FFT is performed. + norm : {None, "ortho"}, optional + .. versionadded:: 1.10.0 + + Normalization mode (see `numpy.fft`). Default is None. Returns ------- @@ -925,10 +1005,10 @@ def ifft2(a, s=None, axes=(-2, -1)): """ - return _raw_fftnd(a, s, axes, ifft) + return _raw_fftnd(a, s, axes, ifft, norm) -def rfftn(a, s=None, axes=None): +def rfftn(a, s=None, axes=None, norm=None): """ Compute the N-dimensional discrete Fourier Transform for real input. @@ -954,6 +1034,10 @@ def rfftn(a, s=None, axes=None): axes : sequence of ints, optional Axes over which to compute the FFT. If not given, the last ``len(s)`` axes are used, or all axes if `s` is also not specified. + norm : {None, "ortho"}, optional + .. versionadded:: 1.10.0 + + Normalization mode (see `numpy.fft`). Default is None. Returns ------- @@ -1007,15 +1091,16 @@ def rfftn(a, s=None, axes=None): [ 0.+0.j, 0.+0.j]]]) """ - - a = asarray(a).astype(float) + # The copy may be required for multithreading. + a = array(a, copy=True, dtype=float) s, axes = _cook_nd_args(a, s, axes) - a = rfft(a, s[-1], axes[-1]) + a = rfft(a, s[-1], axes[-1], norm) for ii in range(len(axes)-1): - a = fft(a, s[ii], axes[ii]) + a = fft(a, s[ii], axes[ii], norm) return a -def rfft2(a, s=None, axes=(-2, -1)): + +def rfft2(a, s=None, axes=(-2, -1), norm=None): """ Compute the 2-dimensional FFT of a real array. @@ -1027,6 +1112,10 @@ def rfft2(a, s=None, axes=(-2, -1)): Shape of the FFT. axes : sequence of ints, optional Axes over which to compute the FFT. + norm : {None, "ortho"}, optional + .. versionadded:: 1.10.0 + + Normalization mode (see `numpy.fft`). Default is None. Returns ------- @@ -1045,9 +1134,10 @@ def rfft2(a, s=None, axes=(-2, -1)): """ - return rfftn(a, s, axes) + return rfftn(a, s, axes, norm) -def irfftn(a, s=None, axes=None): + +def irfftn(a, s=None, axes=None, norm=None): """ Compute the inverse of the N-dimensional FFT of real input. @@ -1080,6 +1170,10 @@ def irfftn(a, s=None, axes=None): `len(s)` axes are used, or all axes if `s` is also not specified. Repeated indices in `axes` means that the inverse transform over that axis is performed multiple times. + norm : {None, "ortho"}, optional + .. versionadded:: 1.10.0 + + Normalization mode (see `numpy.fft`). Default is None. Returns ------- @@ -1128,15 +1222,16 @@ def irfftn(a, s=None, axes=None): [ 1., 1.]]]) """ - - a = asarray(a).astype(complex) + # The copy may be required for multithreading. + a = array(a, copy=True, dtype=complex) s, axes = _cook_nd_args(a, s, axes, invreal=1) for ii in range(len(axes)-1): - a = ifft(a, s[ii], axes[ii]) - a = irfft(a, s[-1], axes[-1]) + a = ifft(a, s[ii], axes[ii], norm) + a = irfft(a, s[-1], axes[-1], norm) return a -def irfft2(a, s=None, axes=(-2, -1)): + +def irfft2(a, s=None, axes=(-2, -1), norm=None): """ Compute the 2-dimensional inverse FFT of a real array. @@ -1149,6 +1244,10 @@ def irfft2(a, s=None, axes=(-2, -1)): axes : sequence of ints, optional The axes over which to compute the inverse fft. Default is the last two axes. + norm : {None, "ortho"}, optional + .. versionadded:: 1.10.0 + + Normalization mode (see `numpy.fft`). Default is None. Returns ------- @@ -1166,4 +1265,4 @@ def irfft2(a, s=None, axes=(-2, -1)): """ - return irfftn(a, s, axes) + return irfftn(a, s, axes, norm) |