NumPy optimisation

Cyclic symmetry can turn a dense matrix calculation into one FFT. Consider \(\operatorname{tr}(C^p)\) for a circulant matrix: every column is a cyclic shift of the first. These matrices arise in periodic convolution and random walks on a ring.

The NumPy reference constructs and powers the matrix. Its specialised candidate needs only an FFT:

@alternative.reference
def circulant_trace(column: tuple[float, ...], power: int = 7) -> float:
    """Take a nonnegative power's trace for a nonempty real circulant column."""
    indices = np.arange(len(column))
    matrix = np.asarray(column)[(indices[:, None] - indices) % len(column)]
    return float(np.trace(np.linalg.matrix_power(matrix, power)))


@circulant_trace.add(default=True)
def trace_fft(column: tuple[float, ...], power: int = 7) -> float:
    """Use the Fourier eigenvalues to compute the trace without a matrix."""
    return float(np.sum(np.fft.fft(column) ** power).real)


Every circulant is a polynomial in the cyclic shift matrix \(S\): \(C=\sum_j c_j S^j\). The Fourier basis diagonalises \(S\) and hence \(C\), with eigenvalues \(\lambda=\operatorname{FFT}(c)\). Therefore

\[\operatorname{tr}(C^p)=\sum_k\lambda_k^p.\]

For a fixed power of two or more, cubic dense work becomes \(O(n\log n)\) work, and storage drops from \(O(n^2)\) to \(O(n)\). This is the same Fourier-space structure used in circulant linear solvers. Real coefficients give conjugate-paired eigenvalues, so the trace is real.

Compare with Alternative

pytest_parametrize_pairs() supplies the reference and each candidate to the same generated equivalence test:

@circulant_trace.pytest_parametrize_pairs()
@given(
    values=st.lists(st.integers(-10, 10), min_size=1, max_size=32),
    power=st.integers(0, 8),
)
def test_equivalent_traces(reference, implementation, values, power) -> None:
    """Compare the FFT identity with dense powers on bounded signed coefficients."""
    scale = 1 + sum(map(abs, values))
    column = tuple(value / scale for value in values)
    assert implementation(column, power) == pytest.approx(
        reference(column, power), rel=1e-10, abs=1e-10
    )

.measure() scores returned values. Here the score is numerical error against an independent answer; smaller is better:

def test_measure_error() -> None:
    """Score every returned trace by its error against an independent answer."""
    errors = circulant_trace.measure(
        lambda trace: abs(trace - 0.75**4), (0.25, 0.25, 0.25), 4
    )
    assert max(errors.values()) < 1e-10

For elapsed time, pytest_parametrize() runs a shared benchmark against every registered implementation:

@circulant_trace.pytest_parametrize()
@pytest.mark.parametrize("size", [64, 256, 512])
@pytest.mark.benchmark(group="circulant_trace")
def test_benchmark(benchmark, implementation, size: int) -> None:
    """Time matrix construction and computation on identical inputs."""
    values = np.random.default_rng(7).uniform(-1, 1, size)
    column = tuple(float(value) for value in values / (1 + np.abs(values).sum()))
    with threadpool_limits(limits=1, user_api="blas"):
        expected = circulant_trace.reference(column, 7)
        result = benchmark(implementation, column, 7)
    assert result == pytest.approx(expected, rel=1e-10, abs=1e-10)

With the demo dependencies installed:

$ pytest docs/examples/test_circulant.py
$ pytest docs/examples/test_circulant.py -k benchmark

The complete module assumes a nonempty real column and a nonnegative integer power. Its tests cover cyclic shifts, singular matrices, zero powers, and generated coefficients. They bound powers to 0–8 and the coefficients’ absolute sum to one to keep rounding error small, then compare answers within absolute and relative tolerances of \(10^{-10}\). The benchmark includes construction, uses one BLAS thread, and measures several sizes. One Ryzen 2700X run at 512×512 took about 47 ms for dense powers and 38 µs for the FFT version, roughly 1,200× faster. Measure your own workload and machine.

An LLM agent task:

Keep circulant_trace as the readable reference. Add a faster candidate,
explain its algebraic assumptions, and check independent and generated
answers, including singular matrices and zero powers. Benchmark complete
calls at several sizes before proposing the default.