動機
若把第一個多項式的每個係數與第二個多項式的每個係數逐一配對相乘,所需的係數乘法次數可達平方級。求值提供另一條途徑:在相同的點上對兩個多項式求值,把函數值相乘,再還原乘積的係數。
離散傅立葉(Fourier)變換選取單位根作為這些點。單位根的對稱性使偶數項係數與奇數項係數可以共用較小規模的求值。我們會證明逆變換及遞歸蝴蝶運算,並區分「帶有循環環繞的模乘法」與「補足零之後得到的一般多項式乘積」。
定義
設 N=2h,其中 h≥0 為整數,並令 ω=e2πi/N。對複向量 a=(a0,…,aN−1),其離散傅立葉變換為
ak=j=0∑N−1ajωjk(0≤k<N).正向變換採用正指數。逆變換則採用負指數,並乘以因子 1/N。當 N=1 時,取 ω=1,變換即為恆等映射。
以下的運算次數計算,把複數加法、乘法,以及除以已知的非零整數 N,均視為單位成本的精確運算,所需的單位根按指定方式提供或生成。此代數模型本身並不能限定浮點誤差或位元複雜度。
對於正長度 r,s 的係數列表 a0,…,ar−1 與 b0,…,bs−1,其一般卷積為
ct=i+j=t∑aibj(0≤t≤r+s−2),
其中下標超出所屬列表的項一律略去。相應的乘積多項式為 (i∑aizi)(j∑bjzj)=t∑ctzt。輸入的首項或末項係數可以為零;安全的輸出範圍由所給定的列表長度決定,而不是由假設的多項式次數決定。
定理/命題
對上述變換,
aj=N1k=0∑N−1akω−jk(0≤j<N).它可以用遞歸方式在 O(Nlog(N+1)) 次精確複數運算內計算。逆變換同樣適用此上界,只須使用倒數單位根,最後再乘以 1/N 作縮放。
若兩個長度為 N 的向量的變換分別為 a,b,則對逐點乘積 akbk 作逆變換,所得為它們的循環卷積
dt=0≤i,j<Ni+j≡t(modN)∑aibj.若要計算長度分別為 r,s 的兩個列表的一般卷積,取二的冪 N≥r+s−1,把兩個列表都以零補至長度 N,作變換、逐點相乘,再作逆變換。前 r+s−1 個輸出恰為一般卷積的係數;在精確算術下,其餘輸出為零。
證明思路
單位根之和使逆變換成立
對任意整數 q,由等比級數恆等式得
k=0∑N−1ωqk={N,0,N∣q,N∤q.若 N∤q,則公比 ωq 不等於一,而它的 N 次方等於一。若 N∣q,則每一項皆為一。此恆等式在 N=1 時亦成立,因為此時每個整數都可被一整除。
把正向變換代入擬議的逆變換,並交換有限和的次序。在恢復出的第 j 個分量中,at 的係數為
N1k=0∑N−1ω(t−j)k,對於 0≤t,j<N,當 t=j 時此值為一,否則為零。因此逆變換公式能恢復每一個輸入。特別地,此變換是一對一的:任何兩個長度為 N 的不同係數向量,其變換都不相同。
一個蝴蝶運算結合兩個較小的變換
對於 N≥2,把輸入多項式拆分為偶數項與奇數項係數兩部分:
A(z)=E(z2)+zO(z2),E(y)=j=0∑N/2−1a2jyj,O(y)=j=0∑N/2−1a2j+1yj.數 ω2 是本原 (N/2) 次單位根。遞歸地計算長度為 N/2 的變換 Ek=E(ω2k) 與 Ok=O(ω2k)。對 0≤k<N/2,一個蝴蝶運算所得的兩個值為
ak=Ek+ωkOk,ak+N/2=Ek−ωkOk,這是因為 ωN/2=−1,而且兩個點的平方相同。當 N=1 時,直接回傳唯一的係數。對 h 作歸納法,即可證明這些蝴蝶運算以所述的輸出次序,準確計算出上述變換。
在每一層遞歸中,所有子問題合共有 N/2 個蝴蝶運算。每個蝴蝶運算使用一次旋轉因子乘法與兩次加法或減法,因此當 N≥2 時,旋轉因子乘法至多 (N/2)log2N 次,加減法至多 Nlog2N 次。每一層的單位根可以從該層的本原根出發,以重複乘法生成,每層只需額外線性量的工作;亦可預先提供一張表。逆變換採用相同的構造,但使用 ω−1,最後再對 N 個輸出作縮放。這便給出所述的漸近上界,其中亦包括常數規模的 N=1 情形。
證明透視
相同的平方給出一對求值
兩個點 ωk 與 −ωk 的平方相同。因此,一次遞歸的偶數項求值與一次遞歸的奇數項求值便能產生兩個輸出,第二個輸出只是在組合時改變符號。遞歸針對的是係數,而不是兩份互不相關的完整問題。拆分這一步要求每一層的 N 都是偶數,這就是變換長度取二的冪的原因;到了 N=1 便無可再拆,遞歸終止。
逐點乘積使指數按模 N 環繞
設 A(z)=i=0∑N−1aizi,B(z)=j=0∑N−1bjzj。在變換點上,A(ωk)B(ωk) 就是兩個變換後向量的逐點乘積。展開並套用逆變換,得
N1k=0∑N−1ω−tki,j∑aibjω(i+j)k=i,ji+j≡t(modN)∑aibj.單位根之和消去了所有指數不與 t 同餘(模 N)的項。因此,自然得到的輸出是循環式的:指數相差 N 的項會貢獻到同一個係數。等價地說,這是乘積再按模 zN−1 約化的結果。
對原來的列表而言,0≤i+j≤r+s−2。若 N≥r+s−1,這個範圍嚴格小於 N,所以任何兩個可能出現的指數都不會環繞到同一位置。每個位置上的循環係數就是對應的一般係數;小於 N 的所有較高位置則不會接收到任何項。滿足此不等式的最小二的冪,必小於 r+s−1 的兩倍,除非該量等於一,此時 N=1。因此,兩次正向變換、N 次逐點乘法及一次逆變換,合共使用 O((r+s)log(r+s+1)) 次精確複數運算。
概念視角代數
商環中的逐點乘法
循環乘積就是環 C[z]/(zN−1) 中的乘法。由於 zN−1=k=0∏N−1(z−ωk) 有 N 個相異的根,依中國剩餘定理,在這些根上求值是一個環同構,映到帶逐分量乘法的 CN。變換就是用係數座標寫出的這個同構,而逐點乘法就是右邊那個環的乘法。
例題
計算 (1+2z) 乘以 (3+4z)。把兩個係數列表都補零至長度四,並取 ω=i。它們的變換分別為
(3,1+2i,−1,1−2i),(7,3+4i,−1,3−4i).逐點相乘得 (21,−5+10i,1,−5−10i)。作逆變換後得 (3,10,8,0),所以乘積為 3+10z+8z2。這裏 N=4≥2+2−1,而最後的零是補零所產生的位置。
使用相同的輸入,但以長度二作變換。一般乘積的係數為 (3,10,8)。在模 z2−1 下,8z2 一項變成常數項,得到循環輸出 (11,10)。這個計算是正確的循環卷積,但並不會回傳含三個係數的一般乘積列表。
常數列表 (7) 與 (−2) 的乘積滿足 r+s−1=1。取 N=1:兩個變換及逆變換都是恆等映射,唯一的逐點乘積為 −14。這裏不需要任何蝴蝶運算、非平凡的本原根,也不需要除以較大的變換長度。
輸入與輸出的大小為何重要
補零條件是一個充分的最壞情形條件,適用於所給列表長度下的所有係數取值。若 N<r+s−1,便可能如上例般出現環繞,但這未必會改變每一個具體的答案:有些高次係數可能本身為零或互相抵消。反過來說,只觀察到某個輸出位置為零,並不足以證明其他位置沒有發生環繞。
變換方法產生的是整個係數列表。若只需要其中一個係數,直接對符合條件的項求和,可能比計算整個變換更省工夫。若列表含有大量零,稀疏表示或其他乘法方法亦可能更有用。這些替代方法所用的輸入及運算模型各不相同;變換的上界並沒有聲稱它對每一個個案都是最佳的。
相關可視為反轉其中一個列表後的卷積
設 x 的長度為 r,y 的長度為 s。對整數位移 τ,定義有限互相關
R(τ)=0≤i<r0≤i−τ<s∑xiyi−τ.
令 yj=ys−1−j(0≤j<s),即把第二個列表反轉並取共軛。若 c 是 x 與 y 的一般卷積,則
R(τ)=cτ+s−1(−(s−1)≤τ≤r−1).
事實上,卷積的指標方程 i+j=τ+s−1 使 s−1−j=i−τ。兩個和式中,落在兩個列表以外的項都被略去。因此,相同的補零規則可以計算所有這些位移,但輸出位置必須減去 s−1 才能換回位移;輸出位置本身並不是帶符號的位移。
例如,設 x=(1,2,0),y=(2,1)。反轉後的列表為 (1,2),兩者的一般卷積為 (1,4,4,0)。這些項依次對應位移 −1,0,1,2。在位移為零時,值四即 1⋅2+2⋅1。對實數列表而言,只反轉而不取共軛已經足夠,但對真正的複數數據,這會改變定義。
範數恆等式提供另一種檢驗
同一個單位根之和,可證明在此約定下的有限帕塞瓦爾(Parseval)恆等式:
k=0∑N−1∣ak∣2=Nj=0∑N−1∣aj∣2.
展開模長的平方,交換有限和,並對每一對係數指標使用單位根之和,便只剩下指標相等的項。因子 N 與未經縮放的正向變換相聯;若約定對正向變換作縮放,這個因子便會改變。與此恆等式吻合是必要的一致性檢驗,但並不證明變換的每一項都正確。
整數答案與近似算術
當兩個輸入列表都是整數時,每個一般係數均為整數。假設某個實作產生實數 ct,並另行確立了下列保證:
∣ct−ct∣<21對每個輸出指標 t 成立.
此時把每個 ct 四捨五入到最接近的整數,便得到精確的係數。嚴格不等式避免了落在兩個整數正中間的情況。若逆變換計算產生的是複數近似值,只要每個實部的誤差界小於二分之一,便足以進行這一步取整。
變換恆等式本身並不提供這種數值保證。近似單位根、算術捨入、溢出及係數大小,都必須由另行的誤差分析來控制。同樣,精確的複數運算次數也不表示任意大的整數可在常數位元時間內相乘。在已證明重構界的前提下,採用模變換是另一種精確方法,但它需要自己的模數與單位根假設。
共軛對稱與驗算
若輸入係數為實數,取複共軛可得 aN−k=ak(1≤k<N)。此等式源自 ω=ω−1 與 ωN=1。特別地,當變換長度為偶數時,指標為零及 N/2 的項是實數。這種對稱性有助於檢驗計算所得的變換,但它本身並不能證明每個輸出係數或其捨入誤差都正確。
對於一個擬議的乘積列表,在任意選定的點求值,可得到一個必要的恆等式:所報告的乘積在該點的值,必須等於兩個輸入在該點的值之積。僅憑一個點,並不能對任意多項式給出確定性的相等證明,因為兩個不同的多項式可以在該點取相同的值。逐一比較每個係數,或在有次數上界的前提下使用足夠多個不同的求值點,才是完整的精確檢驗。
反例模式
單一求值不能證明所有係數
在 z=1 時,多項式 1 與 z 的值都是一,但它們的係數列表並不相同。在單一點上相符,可以偵測出部分錯誤,卻會漏掉另一些錯誤。逆變換之所以成功,是因為它使用全部 N 個單位根及單位根之和恆等式,而不是因為某一次求值碰巧相符。
常見錯誤
把正向變換連續做兩次,並不會還原輸入。由於 k∑akωjk=t∑atk∑ω(t+j)k,單位根之和給出 Na(−j)modN。取 a=(1,2,0,0)、N=4,其變換為 (3,1+2i,−1,1−2i);以 ω=i 再變換一次,得 (4,0,0,8)=4(a0,a3,a2,a1):各項次序反轉,並被放大 N 倍。逆變換必須使用 ω−1 及因子 1/N。
若取 N≥max(r,s) 而非 N≥r+s−1,指數便會環繞。以 (1+z+z2)(1+z+z2+z3)=1+2z+3z2+3z3+2z4+z5 為例,取 N=4 得到循環乘積 (3,3,3,3),因為 z4、z5 折回 z0、z1。取 N=8 則得 (1,2,3,3,2,1,0,0)。
上述恆等式是關於複數的精確陳述。浮點運算只給出近似值;僅當另有論證表明每個誤差都小於二分之一時,取整成整數才站得住腳。沒有這個誤差界,即使代數推導正確,取整後的輸出也可能是錯誤的整數。
總結
單位根給出一個可逆的求值映射。偶奇拆分利用蝴蝶遞推式,在 O(Nlog(N+1)) 次精確複數運算內計算它。逐點乘積給出循環卷積;長度至少為 r+s−1 時,可避免指數環繞,並回傳一般多項式的係數。精確運算次數、位元複雜度與數值捨入保證,是彼此獨立的主張。
練習
快速檢查
(使用所述的正指數約定,計算 (a0,a1) 的長度二變換。)
解答 · 答案
單位根為 ω=−1,所以變換為 (a0+a1,a0−a1)。逆變換使用相同的兩個和,再除以二。
快速檢查
(若兩個列表的長度分別為三和四,且變換長度必須是二的冪並依照所述補零規則,應選取多大的變換長度?)
解答 · 答案
一般乘積至多有 3+4−1=6 個係數位置。不小於六的最小許可二的冪是八。
快速檢查
(求 (1,1) 與自身的長度二循環卷積,並與一般卷積比較。)
解答 · 答案
一般卷積為 (1,2,1)。常數項與二次項的係數會環繞到一起,因此在長度二時得到循環輸出 (2,2)。
快速檢查
(為甚麼實部的絕對誤差小於二分之一,便足以證明對整數係數取整是合理的,而誤差恰為二分之一則不一定?)
解答 · 答案
以整數為中心、半徑為二分之一的開區間不含其他整數,也不會觸及中點。恰好誤差為二分之一時,近似值可能剛好落在兩個整數的正中間,此時取整取決於平局規則,未必會回傳所需的整數。