一個運算穿著許多戲服
假設你把一個小小的權重視窗沿著一段長訊號滑過去——在每個位置上，你把視窗和它下方的值相乘、再把這些乘積加起來，然後往前一步、重複。這個「滑動加權和」就是卷積，而一旦你學會辨認它，就會開始到處看見它。模糊一張照片，就是把影像和一個小小的鐘形核做卷積。平滑一筆有雜訊的量測，就是把它和一段短短的平均視窗做卷積。移動平均濾波器的輸出、一個聲學房間替聲音添上的回聲、一個電路對輸入的響應——全是卷積。它是整個計算世界裡最普世的運算之一，這正是為什麼把它變快會如此重要。
這裡有個把本篇和前幾篇綁在一起的驚奇：把兩個多項式相乘也是卷積。算 (1 + 2x)(3 + 4x) = 3 + 10x + 8x^2。看那兩串係數 [1, 2] 與 [3, 4]；答案的係數 [3, 10, 8] 正是把它們做卷積得到的——1*3 = 3，再來 1*4 + 2*3 = 10，最後 2*4 = 8。每一個輸出係數，都是「指標相加恰好等於對的總和」的那些輸入係數乘積的和。所以每當你把多項式相乘，你就是在對它們的係數向量做卷積。而既然一個長整數不過是它的底數的一個多項式（1234 = 1*10^3 + 2*10^2 + 3*10 + 4），把巨大的數相乘就是卷積外加進位。同一台機器把這一切全做了。
現在來數一數用最顯然的方式做要花多少。如果一個輸入長度是 M、另一個是 N，卷積會有 M + N - 1 個輸出，而每個輸出是至多 min(M, N) 個乘積的和。當兩個長度都約為 N 時，那大致是 N 個輸出項、每個要花約 N 次乘加——一個 O(N^2) 的演算法。把訊號長度加倍，工作量就變成四倍。對只有寥寥數個抽頭的核這沒問題，但要把兩個長度百萬的向量做卷積（兩個百萬位數的數、兩段長音軌），O(N^2) 就意味著一兆次運算：本想要毫秒，卻得花上幾分鐘到幾小時。我們需要這道 O(N^2) 的牆倒下。
卷積定理：困難的運算變得容易
逃生口是應用數學裡最美的事實之一，卷積定理。它的離散形式說：在原始域裡的卷積，就是頻率域裡單純的逐點相乘。對每個輸入向量取離散傅立葉轉換；把這兩個轉換逐項相乘（只是 N 個彼此獨立的乘積，一個 O(N) 的步驟）；再對結果取逆離散傅立葉轉換。回來的東西，恰好就是這兩個原始向量的卷積。一個跨遍所有指標對、糾纏交錯的和，已經溶解成一個容易的逐元素乘積——只要你透過頻率這片透鏡去看這些資料。
這到底為什麼成立？回想離散傅立葉轉換那一篇：傅立葉基底向量是複指數——純粹的波——而離散傅立葉轉換把你的資料改寫成那些波的和。和一個波做卷積，並不會把波彼此混在一起；它只是把每個波乘上一個數來重新縮放（這正是「指數函數是任何卷積的特徵向量」的意思）。所以在頻率基底裡，每個波都被獨立處理，卷積只能把每個頻率各自拉長或縮短——而獨立地縮放每個座標，恰恰就是逐點相乘。離散傅立葉轉換正是那個把卷積對角化的座標變換。這一句話就是定理成立的全部理由，也是為什麼同一個想法會以特徵分解之姿在本課程別處再度出現。
一個演算範例，以及循環的陷阱
讓我們用快速的方法把 (1 + 2x) 乘上 (3 + 4x)，好在一個我們已經知道答案的東西上看齒輪如何轉動。誠實的答案是 [3, 10, 8]。但有個陷阱我們必須先尊重：長度 N 的離散傅立葉轉換把你的資料當成週期性的，所以把兩個長度 N 的轉換相乘，得到的是循環卷積——那些輸出會繞過末端、折回到開頭疊上去。要拿回我們想要的普通（線性）卷積，就得補零。真正的輸出長度是 2 + 2 - 1 = 3，所以我們把兩個係數向量都補到長度 4（下一個 2 的冪，快速傅立葉轉換喜歡這個）：[1, 2, 0, 0] 與 [3, 4, 0, 0]。那些補上的零，給繞回來的東西一塊無害可落腳的空房間。
Goal: convolve [1,2] with [3,4] == multiply (1+2x)(3+4x)
1. zero-pad to length 4:
a = [1, 2, 0, 0]
b = [3, 4, 0, 0]
2. forward FFT (length 4):
A = FFT(a) = [ 3, 1-2i, -1, 1+2i ]
B = FFT(b) = [ 7, 3-4i, -1, 3+4i ]
3. pointwise multiply A .* B (entry by entry):
C = [ 21, (1-2i)(3-4i), 1, (1+2i)(3+4i) ]
= [ 21, -5-10i, 1, -5+10i ]
4. inverse FFT:
c = IFFT(C) = [ 3, 10, 8, 0 ] <-- the coefficients!
(3 + 10x + 8x^2, exactly the schoolbook product.)
direct cost ~ N^2 ; this route ~ N log N for large N.從這個小範例得出兩條誠實的提醒。第一，那些快速傅立葉轉換步驟裡的每個數都是複數、都在浮點數裡算出來，所以逆轉換不會回給你一個乾淨的整數 10——它回給你的是 10.00000000000003 之類，你在最後才四捨五入。對整數而言這沒問題，但它意味著快速卷積給的是一個受捨入左右的近似答案，正是本級反覆出現的教訓。第二，忘了補零是經典的臭蟲：少了它，你會悄悄算成循環卷積，繞回來的東西汙染你最前面幾個輸出，結果看起來合理卻是錯的。在轉換之前，永遠把兩個輸入都補到至少 M + N - 1 那麼長。
快速何時其實很慢，以及隨之而來的近親
快速卷積並非永遠是對的工具，好的工程師知道何時該跳過它。快速傅立葉轉換這條路帶著固定的開銷——三次轉換、補零、複數運算——只有當 N 夠大時才划得來。如果你要把一段長訊號和一個極小的核做卷積（比方說一個 5 抽頭的平滑濾波器），直接的滑動和只要約 5N 次運算，這勝過帶著沉重常數的 O(N log N) 快速傅立葉轉換路線。交叉點通常落在幾十個抽頭左右的核。誠實的法則是：核短就直接做；只有當兩個運算元都真的很長時，才伸手去拿快速傅立葉轉換。
第二個皺褶：如果其中一個運算元沒有盡頭呢？在即時音訊裡，訊號永無止境地串流進來，而核（比方說一個殘響脈衝）是固定的。你無法等到整段訊號到齊才去轉換。修法是重疊相加（以及它的手足重疊保留）：把那條長串流切成一塊塊，把每一塊和核做快速傅立葉轉換卷積，再把重疊的尾巴加回去。這拿回了精確的線性卷積，同時讓每一次快速傅立葉轉換都維持在可控的大小、延遲也很低。它就是被改造去適應串流世界的快速卷積，也是每一套音訊工作站裡卷積殘響外掛內部所跑的東西。
退一步，留意一個想法能伸得多遠。同一個卷積定理的把戲——轉換、逐點相乘、轉換回來——是把百萬位數相乘背後的主力（電腦代數系統裡 Schonhage-Strassen 風格的整數乘法）、是把兩段訊號對齊以找出匹配的互相關搜尋背後的主力，也是支撐糾錯碼的多項式算術背後的主力。它甚至預示了本級壓軸的快速卜松求解器，在那裡轉換一張網格，會把一個微分方程變成一個你靠簡單除法就能解的對角方程。每當一個問題暗地裡其實是卷積，快速傅立葉轉換就把 O(N^2) 變成 O(N log N)，一個原本無望的計算就變成例行公事。