Strassen, FFT ve sayısal maliyet

Klasik n×n matris çarpımı üç döngüyle Θ(n³) aritmetik işlem yapar. Strassen, bloklara bölünmüş iki matrisi sekiz yerine yedi alt çarpımla birleştirir: T(n)=7T(n/2)+Θ(n²), yani Θ(n^log₂7). Ek toplama, geçici alan, cache davranışı ve sayısal hata nedeniyle küçük matrislerde daha iyi değildir. Modern AI sistemlerinin bütün matris çarpımlarını Strassen ile yaptığı söylenemez; donanım ve kernel seçimi önemlidir.

FFT bir polinomu uygun köklerde değerlendirerek convolution hesaplamasını hızlandırır. Katsayılar arasında doğrudan convolution Θ(n²), FFT tabanlı yöntem uygun uzunlukta O(n log n) aritmetik işlemdir. Circular ve linear convolution farklıdır; yeterli zero-padding yapılmazsa sonuç sarılır. Floating-point FFT sonrası yuvarlama hatası kontrol edilmelidir.

NTT uygun asal modül ve birim köklerle exact modular convolution sağlar. CRT ile daha büyük katsayılar yeniden kurulabilir, fakat sınırları kanıtlanmalıdır. Aritmetik işlem sayısı ile büyük tamsayı bit maliyeti aynı ölçüm değildir. BLAS, SIMD, GPU ve tiling çoğu gerçek uygulamada asimptotik değişim kadar önemlidir.

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]