利用快速傅里葉變換(FFT)計(jì)算多項(xiàng)式乘法

1、利用快速傅里葉變換(FFT)計(jì)算多項(xiàng)式乘法作者:宋振華摘要本文將討論快速傅里葉變換(FFT)，利用FFT設(shè)計(jì)一種算法，使多項(xiàng)式相乘的時(shí)間復(fù)雜度降低為0(nlog2n),以便在計(jì)算機(jī)上高效計(jì)算多項(xiàng)式乘法.關(guān)鍵詞:快速傅里葉變換、多項(xiàng)式乘法目錄一、引言二、算法概述三、引理1、多項(xiàng)式的表示系數(shù)表達(dá)形式點(diǎn)值表達(dá)形式插值2、利用離散傅里葉變換(DFT)與FFT導(dǎo)出結(jié)果的點(diǎn)值表達(dá)形式單位復(fù)數(shù)根離散傅里葉變換(DFT)通過快速傅里葉變換(FFT)計(jì)算向量y3、利用FFT計(jì)算逆DFT,將結(jié)果的點(diǎn)值表達(dá)形式化為系數(shù)表達(dá)形式在單位復(fù)數(shù)根處插值利用FFT計(jì)算逆DFT四、算法具體流程五、算法的實(shí)際應(yīng)用:計(jì)算大整數(shù)乘法

2、六、參考文獻(xiàn)、引言基于FFT的離散傅里葉變換(DFT)技術(shù)，是當(dāng)今信息傳輸、頻譜分析等領(lǐng)域中最重要的數(shù)學(xué)工具之一.在計(jì)算機(jī)編程中,我們經(jīng)常需要計(jì)算兩個(gè)多項(xiàng)式函數(shù)的乘積對(duì)于兩個(gè)n次多項(xiàng)式函數(shù)，計(jì)算其乘積最直接方法所需時(shí)間為C2)本文將討論快速傅里葉變換(FFT),利用FFT設(shè)計(jì)一種算法，使多項(xiàng)式相乘的時(shí)間復(fù)雜度降低為0(nlog2n),以便在計(jì)算機(jī)上高效執(zhí)行.二、算法概述通過FFT進(jìn)行離散傅里葉變換，將兩個(gè)多項(xiàng)式由系數(shù)表達(dá)形式轉(zhuǎn)化為點(diǎn)值表達(dá)形式.將這2個(gè)點(diǎn)值表達(dá)形式的多項(xiàng)式相乘，得到結(jié)果的點(diǎn)值表達(dá)形式.最后利用FFT做DFT的逆,得到結(jié)果的系數(shù)表達(dá)形式.三、引理1、多項(xiàng)式的表示系數(shù)表達(dá)對(duì)于次數(shù)為

3、n的多項(xiàng)式A(x)=Yaxi,其系數(shù)表達(dá)是一個(gè)由系數(shù)組成ii=0TOC o 1-5 h z HYPERLINK l bookmark6 o Current Document 的向量a=(a,aa01n考慮用系數(shù)形式表示、次數(shù)為n的多項(xiàng)式A(x)、B(x)的乘法運(yùn)算.記C(x)=A(x)B(x)=藝cxi有c=ab.可以看出，采取逐個(gè)計(jì)iiji-ji=0j=0算c(0i2n,iGN)的方式進(jìn)行求解，其時(shí)間復(fù)雜度為0(n2)i點(diǎn)值表達(dá)定義：一個(gè)次數(shù)為n的多項(xiàng)式A(x)的點(diǎn)值表達(dá)就是由一個(gè)有n個(gè)點(diǎn)值對(duì)組成的集合(x,y)10in,igN,y=A(x),使得對(duì)于k=0,1,2,.,n,所有iiii的x

4、各不相同.k點(diǎn)值表達(dá)下多項(xiàng)式乘法對(duì)于n次多項(xiàng)式A(x),B(x)，設(shè)其點(diǎn)值表達(dá)式分別為：A(x):(x,y),(x,y),(x,y)，,(x,y),001122nnB(x):(x,y,),(x,y，),(x,y,),.,(x,y,)001122nn設(shè)C(x)=A(x)B(x),由于C(x)的次數(shù)為2n,因此必須對(duì)A(x)和B(x)的點(diǎn)值表達(dá)式進(jìn)行擴(kuò)展,使每個(gè)多項(xiàng)式都包含2n+1個(gè)點(diǎn)值對(duì).給定A,B的擴(kuò)展點(diǎn)值表達(dá):A(x):(x,y),(x,y),(x,y)，,(x,y),0011222n2nB(x):(x,y,),(x,y，),(x,y,),.,(x,y,).0011222n2n,yy,).2

5、n2n則C(x)的點(diǎn)值表達(dá)形式為：(x0，y0y0)，(I,人，(x2,y2打)，(x2n因此，計(jì)算C(x)點(diǎn)值表達(dá)式的時(shí)間復(fù)雜度為0(n).插值求值運(yùn)算的逆(從一個(gè)多項(xiàng)式的點(diǎn)值表達(dá)形式確定其系數(shù)表達(dá)形式)稱為插值下面將證明，n個(gè)點(diǎn)求值運(yùn)算與插值運(yùn)算是定義完備的互逆運(yùn)算.a.多項(xiàng)式的點(diǎn)值表達(dá)可以唯一確定多項(xiàng)式的系數(shù)表達(dá)形式.多項(xiàng)式的點(diǎn)值表達(dá)等價(jià)于矩陣方程:卩xx2、xn(a)(y)000001xx2xnay111111xx2xna=y:22222Jxnx2nxn丿na丿ny丿n(3-1-3-a)記系數(shù)矩陣為V,由Vandermonde行列式可知，|V|=nC-x)ij0ijn而Vi,jgN,0

6、i,jn,i豐j，有x豐x，因此|V|豐0，即V可逆.ij因此對(duì)于給定點(diǎn)值表達(dá),我們能夠唯一確定系數(shù)表達(dá)式,且b.對(duì)于次數(shù)為n的多項(xiàng)式函數(shù)A(x),插值算法基于如下Lagrange公式:(3-1-3-b)n(x一x)A(xLZykn(x-x)k=0kjj豐k容易驗(yàn)證,Lagrange公式的計(jì)算復(fù)雜度為0(n2).i=0因此，n個(gè)點(diǎn)求值運(yùn)算與插值運(yùn)算是定義完備的互逆運(yùn)算，它們將多項(xiàng)式的系數(shù)表達(dá)與點(diǎn)值表達(dá)進(jìn)行相互轉(zhuǎn)化.2、利用離散傅里葉變換(DFT)與FFT導(dǎo)出結(jié)果的點(diǎn)值表達(dá)形式(1)單位復(fù)數(shù)根n次單位復(fù)數(shù)根是滿足On=1的復(fù)數(shù)O.n次單位復(fù)數(shù)根恰好有n個(gè):對(duì)于k=0,1,.,n-1,這些根是en

7、.由Euler公式e二cos)+isin)可知，這n個(gè)單位復(fù)數(shù)根均勻地分布在以復(fù)平面原點(diǎn)為圓心的單位圓圓周2兀上.O二en稱為主n次單位根，所有其他n次單位根都是o的冪次.nnn個(gè)n次單位復(fù)數(shù)根O0,O1,O2,.,On-1在乘法意義下構(gòu)成一個(gè)群,nnnn該群與群同構(gòu)由此，可以得到如下推論：nna.,2加k.2kVn0,k0,d0,有Odk=e加=eln=0k.dnn(3-2-1-a)Vn二2k,kgN*,O2=0=1.n2n若n=2k,kgN*,(0/)210in,igN=(0i)210i,igN.nn/22(3-2-1-c)(3-2-1-b)對(duì)推論c的證明:由a可知，VkGN,C)=Ok/

8、2nn/2所以對(duì)于kGN，ok2，有(Ok+n/2)2=O2k+n=O2kOn=O2k二(Ok)2.得證.nnnnnnd.VngN*,kgN且k不能被n整除，有藝O=0.ni=0(3-2-1-d)對(duì)推論d的證明:藝C)=(Ok)n1nOk-1i=0n(On)k-1(1)k-1Ok-1Ok-1nn離散傅里葉變換(DFT)對(duì)于n次多項(xiàng)式A(x)=工axi,ii=0其系數(shù)形式為a=(a,a,a)T.01n(3-2-2-1)(3-2-2-2)設(shè)y=A(Ok)=aOki,0kn,kGN,knin+1則向量y二(y,yy)T(3-2-2-3)01n就是系數(shù)向量a二(a,a，,a)t的離散傅里葉變換.01n

9、通過快速傅里葉變換(FFT)計(jì)算向量y.對(duì)于n次多項(xiàng)式A(x)=Yaxi,不妨假設(shè)n+1二2p,peN對(duì)于n+1ii=0不為2的整數(shù)次冪的情況類似,此處不再討論.FFT采取了分治策略，采用A(x)中偶數(shù)下標(biāo)與奇數(shù)下標(biāo)的系數(shù)，分別定義兩個(gè)新的次多項(xiàng)式：2Ab(x)=a+ax+ax2hfax2,(3231)024n-1Ali(x)=a+ax+ax2ffax2(3232)135n注意到Ab(x)包含A所有偶數(shù)下標(biāo)的系數(shù)，Abl(x)包含A中所有奇數(shù)下標(biāo)的系數(shù)，于是有：A(x)=Abl(x2)+xAi(x2).(3233)所以，求A(x)在W0,W1,Wn處的值的問題轉(zhuǎn)化為：nf1nf1nf1求次數(shù)為

10、-的多項(xiàng)式A0(x),Ai(x)在點(diǎn)(W0)2,(Wi)2,2nf1nf1(Wn)2處的取值.nf1根據(jù)(2-2-3-3)綜合結(jié)果.根據(jù)(2-2-1-c),式(2-2-3-3)不是由n+1個(gè)不同值組成,而是僅由凹個(gè)出次單位復(fù)數(shù)根所組成，每個(gè)根正好出現(xiàn)2次.因此，我們遞歸22地對(duì)次數(shù)為n的多項(xiàng)式A0(x),A1(x)在nF1個(gè)nF1次單位復(fù)數(shù)根處進(jìn)行求值這些子問題與原始問題形式相同，但規(guī)模變?yōu)橐话?下面確定DFT過程的時(shí)間復(fù)雜度.注意到除了遞歸調(diào)用外，每次調(diào)用需要枚舉a=(a,a，,a)T中所有元素，將a劃分為ab=a,a，a、01n02nat=a,a,a，,a,分別與多項(xiàng)式A0(x),Au(x

11、)相對(duì)應(yīng).其時(shí)間復(fù)雜135n-1度為0(n)因此,對(duì)運(yùn)行時(shí)間有下列遞推式:T(n)二2T(n)+0(n).(3-2-3-4)求解該遞推式,有T(n)=0(nlogn).(3-2-3-5)2采取快速傅里葉變換，我們可以在0(nlogn)時(shí)間內(nèi)，求出次數(shù)為n2的多項(xiàng)式在n+1次單位復(fù)數(shù)根處的值.3、利用FFT計(jì)算逆DFT將結(jié)果的點(diǎn)值表達(dá)形式化為系數(shù)表達(dá)形式(1)在單位復(fù)數(shù)根處插值n+1根據(jù)(2-1-3-a),我們可以把DFT寫成矩陣乘積y=Va，其中V是nDn+1A。1yiy2Dn+1D2n+1D2n+1D4n+1Dnn+1D2nn+1(a10a1a2(3-3-1-1)CDnn+1D2nn+1CD

12、n2丿n+1易知Vp0.即V可逆.n+1n+1F面證明V-1(i,j)處元素vn+1ijD-ijn11.n+1(3-3-1-2)個(gè)由d適當(dāng)冪次填充成的Vandermonde矩陣.考慮V-1V(i,j)處元素p:n+1n+1ijED-ik+1kjijn+1n+1k-0EDk(j-i)n+1n+1k-0(3-3-1-3)當(dāng)j二i時(shí),p二1；當(dāng)j豐i時(shí)，根據(jù)(2-2-1-d)可知,p二0.ijij滿足V-1Vn+1n+1n(3-3-1-4)給定逆矩陣V-1,可以求出a-(a,a，,a)T.n+101n(3-3-1-5)其中a-1yd-ki.in+1kn+1k-0(2)利用FFT計(jì)算逆DFT比較(3-

13、3-1-5)和(3-2-2-2)可知,對(duì)FFT算法進(jìn)行如下修改,即可計(jì)算出逆DFT:把a(bǔ)與y互換，用o-i替換，并且將計(jì)算結(jié)果每個(gè)元素除以n.因此，我們也可以在0(nlogn)時(shí)間內(nèi)計(jì)算出逆DFT.2四、算法具體流程1、加倍多項(xiàng)式次數(shù)通過加入n個(gè)系數(shù)為0的高階項(xiàng)，把多項(xiàng)式A(x)和B(x)變?yōu)榇螖?shù)為2n的多項(xiàng)式，并構(gòu)造其系數(shù)表達(dá).2、求值通過應(yīng)用2(n+1)階的FFT計(jì)算出A(x)和B(x)長度為2(n+1)的點(diǎn)值表達(dá).這些點(diǎn)值表達(dá)中包含了兩個(gè)多項(xiàng)式在2(n+1)次單位根處的取值.3、逐點(diǎn)相乘把A(x)的值與B(x)的值逐點(diǎn)相乘,可以計(jì)算出C(x)二A(x)B(x)的點(diǎn)值表達(dá)，這個(gè)表示中包含了

14、C(x)在每個(gè)2(n+1)次單位根處的值.4、插值通過對(duì)2(n+1)個(gè)點(diǎn)值應(yīng)用FFT，計(jì)算其逆DFT，就可以構(gòu)造出多項(xiàng)式C(x)的系數(shù)表達(dá).由于1、3的時(shí)間復(fù)雜度為0(n),2、4的時(shí)間復(fù)雜度為0(nlogn)，2因此整個(gè)算法的時(shí)間復(fù)雜度為0(nlogn).2五、算法的實(shí)際應(yīng)用:計(jì)算大整數(shù)乘法在密碼學(xué)等領(lǐng)域中，經(jīng)常需要進(jìn)行大整數(shù)乘法運(yùn)算.如果對(duì)整數(shù)p,q逐位相乘然后相加，其時(shí)間復(fù)雜度為0(logpJog。q).當(dāng)p,q規(guī)模巨大時(shí),這種算法將會(huì)十分低效.因此，我們采取快速傅里葉變換進(jìn)行優(yōu)化.TOC o 1-5 h z HYPERLINK l bookmark58 o Current Docume

15、nt 設(shè)p二a-10n+a10n-i+fa10i+a，其中0a9,aeN,0in,ieNnn-110ii(5-1)q二b10m+b10m-i+b10i+b，其中0b9,beN,0im,ieNmm-110ii(5-2)令多項(xiàng)式A(x)二axnfaxn-1ffax1fa，(5-3)nn-110B(x)二bxmfbxm-1ffbx1fb.(5-4)mm-110(5-5)C(x)二A(x)B(x).注意到p二A(10),q二B(10).因此pq二C(10)二A(10)B(10).(5-6)將大整數(shù)相乘轉(zhuǎn)化為多項(xiàng)式的乘法,應(yīng)用快速傅里葉變換,即可得出結(jié)果.六、參考文獻(xiàn)1、大學(xué)數(shù)學(xué)學(xué)習(xí)指南線性代數(shù)(第二版),山東大學(xué)出版社,劉建亞,吳臻,秦靜,史敬濤,許聞天,張?zhí)斓?金輝,胡發(fā)勝,宿潔,崔玉泉,蔣曉蕓編著2、大學(xué)數(shù)學(xué)線性代數(shù)(第二版),高等教育出版社,上海交通大學(xué)數(shù)學(xué)系線性代數(shù)課程組編著3、Int