0
# Fast Fourier Transform
1

2
CuPy provides comprehensive Fast Fourier Transform operations for GPU-accelerated computation, offering NumPy-compatible FFT functionality supporting 1D, 2D, and N-D transforms with both forward and inverse operations optimized for CUDA and ROCm platforms.
3

4
## Capabilities
5

6
### Core FFT Functions
7

8
Standard discrete Fourier transform functions for complex-to-complex transforms in 1D, 2D, and N-D.
9

10
```python { .api }
11
def fft(a, n=None, axis=-1, norm=None):
12
    """
13
    Compute the one-dimensional discrete Fourier Transform.
14
    
15
    Parameters:
16
        a: array_like - Input array, can be complex
17
        n: int, optional - Length of the transformed axis of the output
18
        axis: int, optional - Axis over which to compute the FFT (default is -1)
19
        norm: {None, 'ortho'}, optional - Normalization mode
20
    """
21

22
def ifft(a, n=None, axis=-1, norm=None):
23
    """
24
    Compute the one-dimensional inverse discrete Fourier Transform.
25
    
26
    Parameters:
27
        a: array_like - Input array, can be complex
28
        n: int, optional - Length of the transformed axis of the output
29
        axis: int, optional - Axis over which to compute the FFT (default is -1)
30
        norm: {None, 'ortho'}, optional - Normalization mode
31
    """
32

33
def fft2(a, s=None, axes=(-2, -1), norm=None):
34
    """
35
    Compute the 2-dimensional discrete Fourier Transform.
36
    
37
    Parameters:
38
        a: array_like - Input array, can be complex
39
        s: sequence of ints, optional - Shape (length of each transformed axis) of the output
40
        axes: sequence of ints, optional - Axes over which to compute the FFT (default is (-2, -1))
41
        norm: {None, 'ortho'}, optional - Normalization mode
42
    """
43

44
def ifft2(a, s=None, axes=(-2, -1), norm=None):
45
    """
46
    Compute the 2-dimensional inverse discrete Fourier Transform.
47
    
48
    Parameters:
49
        a: array_like - Input array, can be complex
50
        s: sequence of ints, optional - Shape (length of each transformed axis) of the output
51
        axes: sequence of ints, optional - Axes over which to compute the FFT (default is (-2, -1))
52
        norm: {None, 'ortho'}, optional - Normalization mode
53
    """
54

55
def fftn(a, s=None, axes=None, norm=None):
56
    """
57
    Compute the N-dimensional discrete Fourier Transform.
58
    
59
    Parameters:
60
        a: array_like - Input array, can be complex
61
        s: sequence of ints, optional - Shape (length of each transformed axis) of the output
62
        axes: sequence of ints, optional - Axes over which to compute the FFT
63
        norm: {None, 'ortho'}, optional - Normalization mode
64
    """
65

66
def ifftn(a, s=None, axes=None, norm=None):
67
    """
68
    Compute the N-dimensional inverse discrete Fourier Transform.
69
    
70
    Parameters:
71
        a: array_like - Input array, can be complex
72
        s: sequence of ints, optional - Shape (length of each transformed axis) of the output
73
        axes: sequence of ints, optional - Axes over which to compute the FFT
74
        norm: {None, 'ortho'}, optional - Normalization mode
75
    """
76
```
77

78
### Real FFT Functions
79

80
Optimized FFT functions for real-valued input data, taking advantage of conjugate symmetry to improve performance and memory usage.
81

82
```python { .api }
83
def rfft(a, n=None, axis=-1, norm=None):
84
    """
85
    Compute the one-dimensional discrete Fourier Transform for real input.
86
    
87
    Parameters:
88
        a: array_like - Input array
89
        n: int, optional - Number of points along transformation axis in the input to use
90
        axis: int, optional - Axis over which to compute the FFT (default is -1)
91
        norm: {None, 'ortho'}, optional - Normalization mode
92
    """
93

94
def irfft(a, n=None, axis=-1, norm=None):
95
    """
96
    Computes the inverse of rfft.
97
    
98
    Parameters:
99
        a: array_like - Input array
100
        n: int, optional - Length of the transformed axis of the output
101
        axis: int, optional - Axis over which to compute the FFT (default is -1)
102
        norm: {None, 'ortho'}, optional - Normalization mode
103
    """
104

105
def rfft2(a, s=None, axes=(-2, -1), norm=None):
106
    """
107
    Compute the 2-dimensional FFT of a real array.
108
    
109
    Parameters:
110
        a: array - Input array, taken to be real
111
        s: sequence of ints, optional - Shape of the FFT
112
        axes: sequence of ints, optional - Axes over which to compute the FFT (default is (-2, -1))
113
        norm: {None, 'ortho'}, optional - Normalization mode
114
    """
115

116
def irfft2(a, s=None, axes=(-2, -1), norm=None):
117
    """
118
    Computes the inverse of rfft2.
119
    
120
    Parameters:
121
        a: array_like - Input array
122
        s: sequence of ints, optional - Shape of the real output
123
        axes: sequence of ints, optional - Axes over which to compute the FFT (default is (-2, -1))
124
        norm: {None, 'ortho'}, optional - Normalization mode
125
    """
126

127
def rfftn(a, s=None, axes=None, norm=None):
128
    """
129
    Compute the N-dimensional discrete Fourier Transform for real input.
130
    
131
    Parameters:
132
        a: array_like - Input array, taken to be real
133
        s: sequence of ints, optional - Shape (length of each transformed axis) of the output
134
        axes: sequence of ints, optional - Axes over which to compute the FFT
135
        norm: {None, 'ortho'}, optional - Normalization mode
136
    """
137

138
def irfftn(a, s=None, axes=None, norm=None):
139
    """
140
    Computes the inverse of rfftn.
141
    
142
    Parameters:
143
        a: array_like - Input array
144
        s: sequence of ints, optional - Shape (length of each axis) of the output
145
        axes: sequence of ints, optional - Axes over which to compute the inverse FFT
146
        norm: {None, 'ortho'}, optional - Normalization mode
147
    """
148
```
149

150
### Hermitian FFT Functions
151

152
FFT functions for Hermitian-symmetric data, which is real-valued in the frequency domain.
153

154
```python { .api }
155
def hfft(a, n=None, axis=-1, norm=None):
156
    """
157
    Compute the FFT of a signal that has Hermitian symmetry, i.e., a real spectrum.
158
    
159
    Parameters:
160
        a: array_like - Input array
161
        n: int, optional - Number of points along transformation axis in the input to use
162
        axis: int, optional - Axis over which to compute the FFT (default is -1)
163
        norm: {None, 'ortho'}, optional - Normalization mode
164
    """
165

166
def ihfft(a, n=None, axis=-1, norm=None):
167
    """
168
    Compute the inverse FFT of a signal that has Hermitian symmetry.
169
    
170
    Parameters:
171
        a: array_like - Input array
172
        n: int, optional - Length of the inverse transform
173
        axis: int, optional - Axis over which to compute the FFT (default is -1)
174
        norm: {None, 'ortho'}, optional - Normalization mode
175
    """
176
```
177

178
### Helper Functions
179

180
Utility functions for working with FFT operations including frequency calculations and shifting.
181

182
```python { .api }
183
def fftfreq(n, d=1.0):
184
    """
185
    Return the Discrete Fourier Transform sample frequencies.
186
    
187
    Parameters:
188
        n: int - Window length
189
        d: scalar, optional - Sample spacing (inverse of the sampling rate, default is 1.0)
190
    """
191

192
def rfftfreq(n, d=1.0):
193
    """
194
    Return the Discrete Fourier Transform sample frequencies for rfft.
195
    
196
    Parameters:
197
        n: int - Window length
198
        d: scalar, optional - Sample spacing (inverse of the sampling rate, default is 1.0)
199
    """
200

201
def fftshift(x, axes=None):
202
    """
203
    Shift the zero-frequency component to the center of the spectrum.
204
    
205
    Parameters:
206
        x: array_like - Input array
207
        axes: int or shape tuple, optional - Axes over which to shift
208
    """
209

210
def ifftshift(x, axes=None):
211
    """
212
    The inverse of fftshift. Although identical for even-length x, the functions differ by one sample for odd-length x.
213
    
214
    Parameters:
215
        x: array_like - Input array
216
        axes: int or shape tuple, optional - Axes over which to shift
217
    """
218
```
219

220
### Configuration
221

222
FFT configuration module for performance tuning and backend selection.
223

224
```python { .api }
225
# Configuration module for FFT performance tuning
226
config = cupy.fft.config
227
```
228

229
## Usage Examples
230

231
```python
232
import cupy as cp
233
import cupy.fft as fft
234
import matplotlib.pyplot as plt
235

236
# 1D FFT example
237
# Generate a signal with two frequency components
238
fs = 1000  # Sample rate
239
t = cp.linspace(0, 1, fs, endpoint=False)
240
signal = cp.sin(2 * cp.pi * 50 * t) + 0.5 * cp.sin(2 * cp.pi * 120 * t)
241

242
# Compute FFT
243
signal_fft = fft.fft(signal)
244
freqs = fft.fftfreq(len(signal), 1/fs)
245

246
# Get magnitude spectrum
247
magnitude = cp.abs(signal_fft)
248

249
# 2D FFT example - Image processing
250
# Create a 2D signal (e.g., an image with periodic patterns)
251
x = cp.linspace(-5, 5, 256)
252
y = cp.linspace(-5, 5, 256)
253
X, Y = cp.meshgrid(x, y)
254
image = cp.sin(X) * cp.cos(Y) + 0.5 * cp.sin(2*X + Y)
255

256
# Compute 2D FFT
257
image_fft = fft.fft2(image)
258
image_fft_shifted = fft.fftshift(image_fft)
259

260
# Get magnitude spectrum
261
magnitude_2d = cp.abs(image_fft_shifted)
262

263
# Real FFT for real-valued signals (more efficient)
264
real_signal = cp.cos(2 * cp.pi * 10 * t) + cp.sin(2 * cp.pi * 25 * t)
265
real_fft = fft.rfft(real_signal)
266
real_freqs = fft.rfftfreq(len(real_signal), 1/fs)
267

268
# Inverse FFT
269
reconstructed_signal = fft.ifft(signal_fft)
270
reconstructed_real = fft.irfft(real_fft)
271

272
# N-dimensional FFT for 3D data
273
volume = cp.random.rand(64, 64, 64)
274
volume_fft = fft.fftn(volume)
275
volume_reconstructed = fft.ifftn(volume_fft)
276

277
# FFT-based convolution
278
def fft_convolve(signal1, signal2):
279
    # Zero-pad to avoid circular convolution
280
    n = len(signal1) + len(signal2) - 1
281
    signal1_padded = cp.zeros(n)
282
    signal2_padded = cp.zeros(n)
283
    signal1_padded[:len(signal1)] = signal1
284
    signal2_padded[:len(signal2)] = signal2
285
    
286
    # Convolution via FFT
287
    result = fft.ifft(fft.fft(signal1_padded) * fft.fft(signal2_padded))
288
    return result[:n].real
289

290
# Apply FFT-based filter
291
def lowpass_filter(signal, cutoff_freq, sample_rate):
292
    signal_fft = fft.fft(signal)
293
    freqs = fft.fftfreq(len(signal), 1/sample_rate)
294
    
295
    # Create filter mask
296
    mask = cp.abs(freqs) <= cutoff_freq
297
    
298
    # Apply filter
299
    filtered_fft = signal_fft * mask
300
    filtered_signal = fft.ifft(filtered_fft)
301
    
302
    return filtered_signal.real
303

304
# Example usage of filter
305
filtered = lowpass_filter(signal, 80, fs)
306

307
# Spectral analysis
308
def compute_power_spectrum(signal, sample_rate):
309
    signal_fft = fft.fft(signal)
310
    freqs = fft.fftfreq(len(signal), 1/sample_rate)
311
    power_spectrum = cp.abs(signal_fft)**2
312
    return freqs[:len(freqs)//2], power_spectrum[:len(power_spectrum)//2]
313

314
freqs_pos, power = compute_power_spectrum(signal, fs)
315

316
# Windowing before FFT to reduce spectral leakage
317
def apply_window(signal, window_type='hann'):
318
    if window_type == 'hann':
319
        window = cp.hanning(len(signal))
320
    elif window_type == 'hamming':
321
        window = cp.hamming(len(signal))
322
    elif window_type == 'blackman':
323
        window = cp.blackman(len(signal))
324
    else:
325
        window = cp.ones(len(signal))
326
    
327
    return signal * window
328

329
windowed_signal = apply_window(signal, 'hann')
330
windowed_fft = fft.fft(windowed_signal)
331
```
332

333
## Performance Considerations
334

335
### Memory Efficiency
336

337
```python
338
# Use real FFT when input is real-valued
339
real_data = cp.random.rand(10000)
340
real_fft = fft.rfft(real_data)  # More memory efficient than fft(real_data)
341

342
# In-place operations when possible
343
data = cp.random.rand(1000) + 1j * cp.random.rand(1000)
344
fft.fft(data, overwrite_x=True)  # Note: overwrite_x not always available, check cuFFT backend
345
```
346

347
### Optimal Sizes
348

349
```python
350
# FFT is most efficient for sizes that are powers of 2
351
optimal_size = 2**int(cp.log2(len(signal)) + 1)  # Next power of 2
352
padded_signal = cp.pad(signal, (0, optimal_size - len(signal)), 'constant')
353
efficient_fft = fft.fft(padded_signal)
354
```
355

356
### Batch Processing
357

358
```python
359
# Process multiple signals simultaneously
360
batch_signals = cp.random.rand(100, 1024)  # 100 signals of length 1024
361
batch_fft = fft.fft(batch_signals, axis=1)  # FFT along each signal
362
```
363

364
Fast Fourier Transform operations in CuPy provide high-performance frequency domain analysis capabilities optimized for GPU acceleration, enabling efficient signal processing, image analysis, and scientific computing with familiar NumPy interfaces while leveraging the parallel processing power of modern GPUs.