Skip to content

FFT

Fast Fourier Transform operations from mechestim.fft. All FFT transforms are counted. Real-valued transforms (rfft) cost roughly half of complex transforms.

Cost Summary

Operation Cost Formula
fft, ifft \(5n \cdot \lceil\log_2 n\rceil\)
fft2, ifft2 \(5N \cdot \lceil\log_2 N\rceil\) where \(N = n_1 \cdot n_2\)
fftn, ifftn \(5N \cdot \lceil\log_2 N\rceil\) where \(N = \prod_i n_i\)
rfft, irfft \(5(n/2) \cdot \lceil\log_2 n\rceil\)
rfft2, irfft2 \(5(N/2) \cdot \lceil\log_2 N\rceil\) where \(N = n_1 \cdot n_2\)
rfftn, irfftn \(5(N/2) \cdot \lceil\log_2 N\rceil\) where \(N = \prod_i n_i\)
hfft, ihfft \(5n_{\text{out}} \cdot \lceil\log_2 n_{\text{out}}\rceil\)
fftfreq, rfftfreq, fftshift, ifftshift \(0\) (free)

Examples

import mechestim as me

with me.BudgetContext(flop_budget=1_000_000) as budget:
    signal = me.random.randn(1024)    # free
    spectrum = me.fft.fft(signal)     # 5 * 1024 * 10 = 51,200 FLOPs
    freqs = me.fft.fftfreq(1024)      # free
    print(f"FFT cost: {budget.flops_used:,}")  # 51,200

API Reference

mechestim.fft._transforms

FFT transform wrappers with FLOP counting.

Cost model: 5 * N * log2(N) for complex DFT of length N (Cooley-Tukey radix-2). Source: Cooley & Tukey (1965); Van Loan, "Computational Frameworks for the FFT" (1992), §1.4.

fft_cost(n)

FLOP cost of a 1-D complex FFT.

Parameters:

Name Type Description Default
n int

Transform length.

 required

Returns:

Type Description
int

Estimated FLOP count: 5 * n * ceil(log2(n)).
Notes

Source: Cooley & Tukey (1965); Van Loan, Computational Frameworks for the FFT (1992), §1.4. Assumes radix-2 Cooley-Tukey algorithm.

Source code in src/mechestim/fft/_transforms.py 
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
def fft_cost(n: int) -> int:
    """FLOP cost of a 1-D complex FFT.

    Parameters
    ----------
    n : int
        Transform length.

    Returns
    -------
    int
        Estimated FLOP count: 5 * n * ceil(log2(n)).

    Notes
    -----
    Source: Cooley & Tukey (1965); Van Loan, *Computational Frameworks
    for the FFT* (1992), §1.4. Assumes radix-2 Cooley-Tukey algorithm.
    """
    if n <= 1:
        return 0
    return 5 * n * math.ceil(math.log2(n))

fftn_cost(shape)

FLOP cost of an N-D complex FFT.

Parameters:

Name Type Description Default
shape tuple of int

Transform shape along each axis.

 required

Returns:

Type Description
int

Estimated FLOP count: 5 * N * sum(ceil(log2(d_i))), where N = prod(shape).
Notes

The multi-dimensional FFT is computed as successive 1-D FFTs along each axis. The cost along axis i is 5 * (N / d_i) * d_i * ceil(log2(d_i)) = 5 * N * ceil(log2(d_i)). Summing over axes gives 5 * N * sum(ceil(log2(d_i))).

Source code in src/mechestim/fft/_transforms.py 
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
def fftn_cost(shape: tuple[int, ...]) -> int:
    """FLOP cost of an N-D complex FFT.

    Parameters
    ----------
    shape : tuple of int
        Transform shape along each axis.

    Returns
    -------
    int
        Estimated FLOP count: 5 * N * sum(ceil(log2(d_i))), where N = prod(shape).

    Notes
    -----
    The multi-dimensional FFT is computed as successive 1-D FFTs along each
    axis. The cost along axis *i* is 5 * (N / d_i) * d_i * ceil(log2(d_i))
    = 5 * N * ceil(log2(d_i)). Summing over axes gives
    5 * N * sum(ceil(log2(d_i))).
    """
    N = 1
    for d in shape:
        N *= d
    if N <= 1:
        return 0
    log_sum = sum(math.ceil(math.log2(d)) for d in shape if d > 1)
    return 5 * N * log_sum

hfft_cost(n_out)

FLOP cost of a Hermitian FFT.

Parameters:

Name Type Description Default
n_out int

Output length.

 required

Returns:

Type Description
int

Estimated FLOP count: 5 * n_out * ceil(log2(n_out)).
Notes

The Hermitian FFT computes the FFT of a signal with Hermitian symmetry, producing real-valued output.

Source code in src/mechestim/fft/_transforms.py 
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
def hfft_cost(n_out: int) -> int:
    """FLOP cost of a Hermitian FFT.

    Parameters
    ----------
    n_out : int
        Output length.

    Returns
    -------
    int
        Estimated FLOP count: 5 * n_out * ceil(log2(n_out)).

    Notes
    -----
    The Hermitian FFT computes the FFT of a signal with Hermitian symmetry,
    producing real-valued output.
    """
    if n_out <= 1:
        return 0
    return 5 * n_out * math.ceil(math.log2(n_out))

rfft_cost(n)

FLOP cost of a 1-D real FFT.

Parameters:

Name Type Description Default
n int

Input length (real-valued).

 required

Returns:

Type Description
int

Estimated FLOP count: 5 * (n // 2) * ceil(log2(n)).
Notes

The real FFT exploits conjugate symmetry, roughly halving the work compared to a full complex FFT.

Source code in src/mechestim/fft/_transforms.py 
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
def rfft_cost(n: int) -> int:
    """FLOP cost of a 1-D real FFT.

    Parameters
    ----------
    n : int
        Input length (real-valued).

    Returns
    -------
    int
        Estimated FLOP count: 5 * (n // 2) * ceil(log2(n)).

    Notes
    -----
    The real FFT exploits conjugate symmetry, roughly halving the work
    compared to a full complex FFT.
    """
    if n <= 1:
        return 0
    return 5 * (n // 2) * math.ceil(math.log2(n))

rfftn_cost(shape)

FLOP cost of an N-D real FFT.

Parameters:

Name Type Description Default
shape tuple of int

Transform shape along each axis.

 required

Returns:

Type Description
int

Estimated FLOP count: 5 * (N // 2) * sum(ceil(log2(d_i))), where N = prod(shape).
Notes

Exploits conjugate symmetry along the last axis, roughly halving the work compared to a full complex N-D FFT.

Source code in src/mechestim/fft/_transforms.py 
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
def rfftn_cost(shape: tuple[int, ...]) -> int:
    """FLOP cost of an N-D real FFT.

    Parameters
    ----------
    shape : tuple of int
        Transform shape along each axis.

    Returns
    -------
    int
        Estimated FLOP count: 5 * (N // 2) * sum(ceil(log2(d_i))), where N = prod(shape).

    Notes
    -----
    Exploits conjugate symmetry along the last axis, roughly halving
    the work compared to a full complex N-D FFT.
    """
    N = 1
    for d in shape:
        N *= d
    if N <= 1:
        return 0
    log_sum = sum(math.ceil(math.log2(d)) for d in shape if d > 1)
    return 5 * (N // 2) * log_sum

mechestim.fft._free

Zero-FLOP FFT utility operations.

fftfreq(n, d=1.0)

FFT sample frequencies. Cost: 0 FLOPs.

Source code in src/mechestim/fft/_free.py 
11
12
13
def fftfreq(n, d=1.0):
    """FFT sample frequencies. Cost: 0 FLOPs."""
    return _np.fft.fftfreq(n, d=d)

fftshift(x, axes=None)

Shift zero-frequency component to center. Cost: 0 FLOPs.

Source code in src/mechestim/fft/_free.py 
27
28
29
def fftshift(x, axes=None):
    """Shift zero-frequency component to center. Cost: 0 FLOPs."""
    return _np.fft.fftshift(x, axes=axes)

ifftshift(x, axes=None)

Inverse of fftshift. Cost: 0 FLOPs.

Source code in src/mechestim/fft/_free.py 
35
36
37
def ifftshift(x, axes=None):
    """Inverse of fftshift. Cost: 0 FLOPs."""
    return _np.fft.ifftshift(x, axes=axes)

rfftfreq(n, d=1.0)

Real FFT sample frequencies. Cost: 0 FLOPs.

Source code in src/mechestim/fft/_free.py 
19
20
21
def rfftfreq(n, d=1.0):
    """Real FFT sample frequencies. Cost: 0 FLOPs."""
    return _np.fft.rfftfreq(n, d=d)