動機
直接計算兩個多項式的乘積,需要計算每一對係數的乘積。求值提供了另一種思路:在足夠多的點上分別計算兩個多項式的值,把得到的值逐點相乘,再作插值。當求值點具有足夠的對稱性、可以重複利用已有計算時,這種方法才會變得快速。
單位根正好提供了這種對稱性。它們的偶次冪與奇次冪把規模為 的變換與兩個規模為 的變換連繫起來。我們將推導這個基二快速傅立葉(Fourier)變換,證明它的逆變換公式,並解釋為甚麼多項式乘法需要補零以避免回繞。
定義
定義 1.7.1
(離散傅立葉變換)
設 ,其中 為整數,並令 。對複向量 ,其離散傅立葉變換定義為
符號約定是定義的一部分,整個計算過程中必須前後一致。逆變換使用相反的指數。我們把精確的複數加法與乘法各算作一次單位運算,並假定所需的單位根均已給出。這是代數運算次數的計數,並不保證浮點計算或任意精度的位元運算只需常數時間。
定理
定理 1.7.2
(基二變換)
對 ,透過對偶數下標與奇數下標的係數遞歸地作變換,離散傅立葉變換可以用 次複數算術運算計算出來。
定理 1.7.3
(逆變換與卷積)
逆變換公式為
如果把兩個有限係數序列補零至某個 2 的冪長度,且該長度不小於它們的普通卷積的長度,那麼對它們的離散傅立葉變換作逐點乘法,再作逆變換,便得到它們的普通卷積。
證明
拆分偶數與奇數下標
證明
(偶奇拆分與蝴蝶運算)
對 ,把變換寫成
由於 ,這兩個和分別是偶數下標向量與奇數下標向量的長度為 的離散傅立葉變換。把它們在 處的值記為 與 。又因為 ,且較短的變換以 為週期重複,所以
這樣成對的更新稱為蝴蝶運算。每一對都兩次使用同一個乘積 。當 時,變換就是 。
設 為算術運算次數,則遞歸拆分給出 ,且 。在每一層遞歸深度上,各子問題的長度之和為 ,而非平凡的層數為 。因此總代價為 。預先計算所有需要的單位根,或以一致的方式生成它們,都可以計入這個運算次數;數值精度則是另一個獨立的問題。
證明透視
為甚麼同樣兩個較小的變換能給出前後兩半輸出
對長度為 的單位根取平方,得到長度為 的單位根。把輸出下標平移 ,較小的變換保持不變,但奇數部分的貢獻變號。因此一對較小變換的值可以提供兩個輸出。
證明逆變換
證明
(以單位根的正交性證明逆變換)
關鍵恆等式是
其中 。若 ,則公比 是非平凡的 次單位根,其等比數列之和為 。若 ,則每一項都等於 。
把正變換代入所提出的逆變換公式,並交換有限和的次序。對於除 以外的每個輸入下標,內層和都為零;在下標 處,內層和等於 ;除以 後恰好剩下 。逆變換同樣可以使用相同的基二遞歸,只需改用 ,最後把所有輸出乘以 。
這個證明也涵蓋 的情形:此時唯一的單位根之和為 ,逆變換返回唯一的輸入。它還說明了為甚麼在某種約定下改變符號,就必須相應地一致修改逆變換。連續兩次應用正變換,而不作適當的反轉與縮放,一般並不是逆變換。
概念視角代數
把變換看成矩陣,把卷積看成對角化
設 為矩陣,其元素為 ,則 。反演恆等式說明 ,因此 。循環卷積 就是用循環矩陣 去乘 ;卷積定理恰好說明 :每個循環矩陣在傅立葉基下都是對角的,其特徵值就是第一列的變換。
求值與唯一性
把向量 與多項式 對應起來。正變換恰好就是在 個根 處對 求值。
命題 1.7.4
(單位根處的取值決定係數)
設 、 為次數小於 的複係數多項式。若對所有 都有 ,則 。
證明
(在互不相同的點上求值決定低次多項式)
這些點兩兩不同。若兩個次數小於 的多項式在所有這些點上取值相同,則它們的差至少有 個不同的根。次數至多為 的非零多項式不可能有這麼多根,所以差必為零。因此這些值唯一地確定係數向量。
零多項式是唯一在這 個根處的取值都為零、且次數小於 的多項式。用線性代數的語言說,求值映射是兩個 維複向量空間之間的單射,因而是雙射;前面給出的逆變換公式把這個雙射明確地寫了出來。這種唯一性解釋了為甚麼只要變換長度足夠大,就可以先求值、再把值相乘、最後插值來還原乘積。但它本身並不能給出快速算法:在 個任意點上直接求值可能需要平方量級的工作量,一般的插值也是如此。蝴蝶遞歸與單位根求和形式的逆變換,利用的正是這些特殊的求值點。
對於實的輸入值,當 時有 ,其中下標按模 理解。這是因為 ,並且共軛對有限和是可分配的。它可以用來檢驗計算出的變換,但不能取代逆變換的證明。當輸入為複數時,這種共軛對稱性不一定成立。
追蹤一次遞歸
在第一層,算法按下標的奇偶性把下標分開。在下一層,每個子問題又把各自的偶數位置與奇數位置分開。如此繼續,直至得到只有一個元素的向量。遞歸實作可以返回每個較短的變換,並立即與其同層的另一半合併;它不需要獨立地計算每個輸出。
對 ,第一次拆分使用原始位置 與 。偶數一半接著拆分為 與 ,奇數一半拆分為 與 。在所有子問題中,每一層都涵蓋全部八個係數位置。在這種遞歸視角下,葉子的排列次序與通常的數值下標次序不同;迭代式的原地實作往往要重新排列數據來配合這種次序。數學上的遞推式並不依賴於某種特定的原地置換。
上述執行時間界給出的是該算法運算次數的上界。它並不證明在每一種計算模型下,所有可能的方法都需要 次運算;也不斷言在固定字長的機器上存在使用精確複數運算的實作。這些都是與代數恆等式相互獨立的問題。
卷積與補零
定義 1.7.5
(循環卷積)
對長度為 的向量,循環卷積定義為
證明
(卷積定理與補零)
它的離散傅立葉變換是逐點乘積 。事實上,把卷積代入變換,交換有限和的次序,並令 。指數分解為 對應的因子與 對應的因子;由於 ,下標按模 約化不改變冪的值。這兩個因子恰好就是 與 。
對普通多項式 與 ,它們的乘積的係數為 ,其中 。選取一個 2 的冪 ,並把兩個向量都補零至長度 。普通乘積中沒有任何非零係數的下標不小於 ,所以按模 約化下標不會產生回繞。對逐點乘積作逆變換,得到全部普通係數,後面跟著若干補零。
對於非空的輸入序列,滿足條件的最小的 2 的冪小於 的兩倍。因此三次快速傅立葉變換加上 次逐點乘法,共使用 次複數運算。空多項式可作為零多項式單獨處理。
反例模式
補零不足會改變乘積
取係數向量 與 ,但使用長度為二的循環變換。它們的普通卷積是 ,而循環回繞會把最後一個係數加到第一個係數上,得到 。在長度為二時作逐點乘法,計算出的是循環結果,而不是三個普通係數。
區分循環乘積與普通乘積
長度為 的循環卷積把相差 的倍數的位置視為同一個位置。例如,普通次數為 的項會貢獻到循環位置二。用多項式的語言說,這是模 的乘法。離散傅立葉變換對這種循環乘積是完全正確的,因為每個求值點都滿足 ;在這些點上的取值無法區分 與 。
對於單個普通乘積,補零可以避免這種歧義。如果最高可能的次數至多為 ,就沒有係數會回繞。取下一個 2 的冪,既支援基二遞歸,又保持這個不等式成立。複雜度界中的輸入長度指的是係數個數,包括明確給出的末尾零;去掉已知的末尾零是可選的預處理步驟。
因此,一個具體的乘法流程包含四步:選取滿足次數界的 2 的冪長度,對兩個輸入補零,對兩個補零後的向量作變換,再對逐點乘積作逆變換。逆變換返回的是該完整長度的向量;其中只有前 項才可能是普通乘積中的非零係數。在實作之前寫清楚這些長度,可以避免意外丟失最高次項。
對於整數係數,人們可能希望先計算近似的複數逆變換,再把每個結果捨入至最接近的整數。只有在證明了每個係數的誤差都嚴格小於二分之一之後,這樣的捨入才是合理的。精確算術下的定理並沒有提供這樣的數值誤差界。精心選擇的有限域變換與重構方法可以避開某些浮點問題,但模數必須含有合適的單位根且足夠大,否則需要組合多個模數。這些進一步的條件不在本文的證明範圍之內。
例題詳解
例題 1.7.6
(四點變換)
對 ,有 。直接代入得到 。第一個輸出是各項之和;由於輸入為實數,第二個與第四個輸出互為共軛。
例題 1.7.7
(一層蝴蝶運算)
對同一個輸入,偶數向量 的兩點變換為 ,奇數向量 的變換為 。對 ,蝴蝶運算給出 與 。對 ,乘以 後得到 與 。
例題 1.7.8
(多項式的平方)
多項式 的係數向量為 。在變換之前,把 補零為 。它的離散傅立葉變換為 ;逐點平方後再作逆變換,得到 。最後的零是補零,而不是額外的非零係數。
例題 1.7.9
(一點的情形)
當 時,離散傅立葉變換與其逆變換都返回輸入值。兩個常數多項式相乘只需要一次逐點乘法,不需要蝴蝶運算,也不需要非平凡的單位根。
常見錯誤
常見錯誤
(混用符號約定)
快速傅立葉變換是計算指定的離散傅立葉變換的算法;變換本身是一個線性映射。正變換的指數採用相反的符號,只有在逆變換與例子也相應調整的前提下,才是一種有效的替代約定。
常見錯誤
(只補零至較長輸入的長度)
逐點乘法對應的是變換長度下的循環卷積。普通多項式乘法需要足夠的補零,以防止下標不小於 的係數回繞到較低的位置。僅僅補零至較長輸入的長度,並不總是足夠。
常見錯誤
(把浮點快速傅立葉變換當作精確)
精確的代數證明並不會自動令浮點實作變得精確。捨入誤差會影響係數,而把數值結果捨入至最接近的整數,需要另外證明誤差界。有限域上的數論變換同樣需要合適的單位根,以及它自身的算術假設。
總結
基二快速傅立葉變換把離散傅立葉變換拆分為偶數與奇數兩個子變換,並用蝴蝶運算把它們合併。單位根的正交性證明了逆變換公式。變換把循環卷積變成逐點乘法,而足夠的補零使它能在所述的複數運算次數界內計算普通的多項式乘積。
練習
快速檢查
(在所述的符號約定下,計算 的兩點離散傅立葉變換。)
先求出 。
解答 · 答案
由於 ,變換為 。
快速檢查
(對 ,計算四點離散傅立葉變換的第一項與第三項 。)
用 ,留意出現的是哪些冪。
解答 · 答案
,,因為 。
快速檢查
(為甚麼用長度為二的循環變換去乘兩個長度為二的係數向量,一般無法還原全部三個普通係數?)
的係數去了哪裏?
解答 · 答案
普通卷積在下標二處可能有非零係數。長度為二的循環卷積把下標二與下標零等同起來,把該係數加到第一項上。補零至不小於三的長度,就可以防止這種回繞。
快速檢查
(解釋為甚麼逆變換要除以 。)
把正變換代入逆變換公式。
解答 · 答案
單位根之和在輸入下標與輸出下標不相等時為零,相等時等於 。因此,把正變換代入逆變換後得到的是 ;除以 即還原 。