1、利用快速傅里葉變換(FFT)計算多項式乘法作者:宋振華摘要本文將討論快速傅里葉變換(FFT),利用FFT設計一種算法,使多項式相乘的時間復雜度降低為,以便在計算機上高效計算多項式乘法.關鍵詞:快速傅里葉變換、多項式乘法目錄1、 引言2、 算法概述三、引理1、多項式的表示(1)系數表達形式(2)點值表達形式(3)插值2、利用離散傅里葉變換(DFT)與FFT導出結果的點值表達形式(1)單位復數根(2)離散傅里葉變換(DFT)(3)通過快速傅里葉變換(FFT)計算向量3、 利用FFT計算逆DFT,將結果的點值表達形式化為系數表達形式(1)在單位復數根處插值(2)利用FFT計算逆DFT四、算法具體流程

2、五、算法的實際應用:計算大整數乘法六、參考文獻1、 引言基于FFT的離散傅里葉變換(DFT)技術,是當今信息傳輸、頻譜分析等領域中最重要的數學工具之一.在計算機編程中,我們經常需要計算兩個多項式函數的乘積.對于兩個次多項式函數,計算其乘積最直接方法所需時間為.本文將討論快速傅里葉變換(FFT),利用FFT設計一種算法,使多項式相乘的時間復雜度降低為,以便在計算機上高效執行.2、 算法概述通過FFT進行離散傅里葉變換,將兩個多項式由系數表達形式轉化為點值表達形式.將這2個點值表達形式的多項式相乘,得到結果的點值表達形式.最后利用FFT做DFT的逆,得到結果的系數表達形式.3、 引理1、 多項式的

3、表示(1)系數表達對于次數為的多項式,其系數表達是一個由系數組成的向量.考慮用系數形式表示、次數為的多項式、的乘法運算.記.有.可以看出,采取逐個計算的方式進行求解,其時間復雜度為.(2)點值表達a.定義:一個次數為的多項式的點值表達就是由一個有個點值對組成的集合,使得對于,所有的各不相同.b.點值表達下多項式乘法對于次多項式,設其點值表達式分別為:,:設,由于的次數為,因此必須對和的點值表達式進行擴展,使每個多項式都包含個點值對.給定,的擴展點值表達:,:.則的點值表達形式為:.因此,計算點值表達式的時間復雜度為.(3)插值 求值運算的逆(從一個多項式的點值表達形式確定其系數表達形式)稱為插

4、值.下面將證明,個點求值運算與插值運算是定義完備的互逆運算.a. 多項式的點值表達可以唯一確定多項式的系數表達形式.多項式的點值表達等價于矩陣方程:=.(3-1-3-a)記系數矩陣為,由Vandermonde行列式可知,.而,有,因此,即可逆.因此對于給定點值表達,我們能夠唯一確定系數表達式,且.b.對于次數為的多項式函數,插值算法基于如下Lagrange公式:.(3-1-3-b)容易驗證,Lagrange公式的計算復雜度為.因此,個點求值運算與插值運算是定義完備的互逆運算,它們將多項式的系數表達與點值表達進行相互轉化.2、 利用離散傅里葉變換(DFT)與FFT導出結果的點值表達形式(1)單位

5、復數根次單位復數根是滿足的復數.次單位復數根恰好有個:對于,這些根是.由Euler公式可知,這個單位復數根均勻地分布在以復平面原點為圓心的單位圓圓周上.稱為主次單位根,所有其他次單位根都是的冪次.個次單位復數根,.,在乘法意義下構成一個群,該群與群同構.由此,可以得到如下推論:a. ,有.(3-2-1-a)b. ,.(3-2-1-b)c. 若,=.(3-2-1-c)對推論c的證明:由a可知,.所以對于,有.得證.d.且不能被整除,有.(3-2-1-d)對推論d的證明:.(2)離散傅里葉變換(DFT)對于次多項式,其系數形式為.(3-2-2-1)設,(3-2-2-2)則向量(3-2-2-3)就是

6、系數向量的離散傅里葉變換.(3)通過快速傅里葉變換(FFT)計算向量.對于次多項式,不妨假設.對于不為的整數次冪的情況類似,此處不再討論.FFT采取了分治策略,采用中偶數下標與奇數下標的系數,分別定義兩個新的次多項式:,(3-2-3-1).(3-2-3-2)注意到包含所有偶數下標的系數,包含中所有奇數下標的系數,于是有:.(3-2-3-3)所以,求在,.,處的值的問題轉化為:a.求次數為的多項式,在點,.,處的取值.b.根據(2-2-3-3)綜合結果.根據(2-2-1-c),式(2-2-3-3)不是由個不同值組成,而是僅由個次單位復數根所組成,每個根正好出現次.因此,我們遞歸地對次數為的多項式

7、,在個次單位復數根處進行求值.這些子問題與原始問題形式相同,但規模變為一半.下面確定DFT過程的時間復雜度.注意到除了遞歸調用外,每次調用需要枚舉中所有元素,將劃分為、,分別與多項式,相對應.其時間復雜度為.因此,對運行時間有下列遞推式:.(3-2-3-4)求解該遞推式,有.(3-2-3-5)采取快速傅里葉變換,我們可以在時間內,求出次數為的多項式在次單位復數根處的值.3、 利用FFT計算逆DFT將結果的點值表達形式化為系數表達形式(1)在單位復數根處插值根據(2-1-3-a),我們可以把DFT寫成矩陣乘積,其中是一個由適當冪次填充成的Vandermonde矩陣.=(3-3-1-1)易知.即可

8、逆.下面證明處元素.(3-3-1-2)考慮處元素:.(3-3-1-3)當時,;當時,根據(2-2-1-d)可知,.滿足.(3-3-1-4)給定逆矩陣,可以求出.其中.(3-3-1-5)(2)利用FFT計算逆DFT比較(3-3-1-5)和(3-2-2-2)可知,對FFT算法進行如下修改,即可計算出逆DFT:把與互換,用替換,并且將計算結果每個元素除以.因此,我們也可以在時間內計算出逆DFT.四、算法具體流程1、加倍多項式次數通過加入個系數為的高階項,把多項式和變為次數為的多項式,并構造其系數表達.2、求值通過應用階的FFT計算出和長度為的點值表達.這些點值表達中包含了兩個多項式在次單位根處的取值

9、.3、逐點相乘把的值與的值逐點相乘,可以計算出的點值表達,這個表示中包含了在每個次單位根處的值.4、插值通過對個點值應用FFT,計算其逆DFT,就可以構造出多項式的系數表達.由于1、3的時間復雜度為,2、4的時間復雜度為,因此整個算法的時間復雜度為.五、算法的實際應用:計算大整數乘法在密碼學等領域中,經常需要進行大整數乘法運算.如果對整數逐位相乘然后相加,其時間復雜度為.當規模巨大時,這種算法將會十分低效.因此,我們采取快速傅里葉變換進行優化.設,其中(5-1) ,其中(5-2)令多項式,(5-3) .(5-4) .(5-5)注意到,.因此.(5-6)將大整數相乘轉化為多項式的乘法,應用快速傅里葉變換,即可得出結果.6、 參考文獻1、 大學數學學習指南線性代數(第二版),山東大學出版社,劉建亞,吳臻,秦靜,史敬濤,許聞天,張天德,金輝,胡發勝,宿潔,崔玉泉,蔣曉蕓編著2、 大學數學線性代數(第二版),高等教育出版社,上海交通大學數學系線性代數課程組編著3、 Introduction to Algorithms(Third Edition),Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest,Clifford