Strassen, FFT and numerical costs

Classical n×n matrix multiplication uses Θ(n³) arithmetic operations. Strassen combines seven half-size products rather than eight: T(n)=7T(n/2)+Θ(n²), yielding Θ(n^log₂7). Extra additions, temporary storage, cache effects and numerical error make it unattractive for small matrices. AI kernels do not universally use Strassen; hardware matters.

FFT accelerates convolution by evaluating polynomials at suitable roots. Direct convolution is Θ(n²); FFT-based convolution takes O(n log n) arithmetic operations at an appropriate padded length. Circular and linear convolution differ: insufficient zero-padding wraps coefficients. Floating-point rounding must be checked.

NTT computes exact modular convolution with suitable primes and roots. CRT can reconstruct larger coefficients only with proven bounds. Arithmetic counts differ from big-integer bit costs. BLAS, SIMD, GPU kernels and tiling are crucial practical factors.

def convolution(a,b):
    out=[0]*(len(a)+len(b)-1)
    for i,x in enumerate(a):
        for j,y in enumerate(b): out[i+j]+=x*y
    return out
assert convolution([1,2],[3,4])==[3,10,8]