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

利用快速傅里葉變換(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)通過(guò)快速傅里葉變換(FFT)計(jì)算向量y3、 利用FFT計(jì)算逆DFT,將結(jié)果的點(diǎn)值表達(dá)形式化為系數(shù)表達(dá)形式在單位復(fù)數(shù)根處插值利用FFT計(jì)算逆DFT四、 算法具體流程五、 算法的實(shí)際應(yīng)用:計(jì)算大整數(shù)乘法六、 參考文獻(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í)行.二、 算法概述通過(guò)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ù)為n的多項(xiàng)式A(x)=Yaxi,其系數(shù)表達(dá)是一個(gè)由系數(shù)組成ii=0TOC\o"1-5"\h\z\o"CurrentDocument"的向量a=(a,a a\?0 1n考慮用系數(shù)形式表示、次數(shù)為n的多項(xiàng)式A(x)、B(x)的乘法運(yùn)算.記C(x)=A(x)B(x)=藝cxi?有c=￡ab.可以看出，采取逐個(gè)計(jì)i i ji-ji=0 j=0算c(0<i<2n,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)10<i<n,igN,y=A(x)},使得對(duì)于k=0,1,2,...,n,所有ii i i的x各不相同.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)},0 0 1 1 2 2 n nB(x):{(x,y,),(x,y，),(x,y,),...,(x,y,)}0 0 1 1 2 2 n n設(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)},0 0 1 1 2 2 2n 2nB(x):{(x,y,),(x,y，),(x,y,),...,(x,y,)}.0 0 1 1 2 2 2n 2n,yy,)}.2n2n則C,yy,)}.2n2n{(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à)于矩陣方程:卩x卩xx2???、xn(a)(y)000001xx2???xnay111111xx2???xna=y:22222Jxnx2???nxn丿n<a丿n<y丿n(3-1-3-a)記系數(shù)矩陣為V,由Vandermonde行列式可知，|V|=nC-x)ij0<i<j<n而Vi,jgN,0<i,j<n,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=0 kj(3-1-3-b)j豐k容易驗(yàn)證,Lagrange公式的計(jì)算復(fù)雜度為0(n2).

因此，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個(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,這些根是e‘n.由Euler公式e￡二cos@)+isin@)可知，這n個(gè)單位復(fù)數(shù)根均勻地分布在以復(fù)平面原點(diǎn)為圓心的單位圓圓周2兀上.O二e'n稱為主n次單位根，所有其他n次單位根都是o的冪次.nnn個(gè)n次單位復(fù)數(shù)根O0,O1,O2,...,On-1在乘法意義下構(gòu)成一個(gè)群,nnn n該群與群<Z，+>同構(gòu)?由此，可以得到如下推論：nna.,, 2加k .2^kVn>0,k>0,d>0,有Odk=e'加=eln=0k.dn n(3-2-1-a)Vn二2k,kgN*,O2=0=—1.n2n若n=2k,kg N*, {(0/)210<i< n,i gN}={(0i )210<i< ,i gN}.n n/2 2(3-2-1-c)(3-2-1-b)對(duì)推論c的證明:由a可知，VkGN,C)=Ok/2?n n/2所以對(duì)于kGN，o<k<2，有(Ok+n/2)2=O2k+n=O2kOn=O2k二(Ok)2.得證.n n nnnnd.VngN*,kgN且k不能被n整除，有藝O=0.ni=0(3-2-1-d)對(duì)推論d的證明:藝C)=(Ok)n―1n Ok-1i=0 n(On)k-1 (1)k-1Ok-1Ok-1

nn對(duì)于n次多項(xiàng)式A(x)=工axi,ii=0其系數(shù)形式為a=(a,a, ,a)T.0 1 n(3-2-2-1)(3-2-2-2)設(shè)y=A(Ok)=aOki,0<k<n,kGN,k n i n+1(3-2-2-1)(3-2-2-2)則向量y二(y,yy)T (3-2-2-3)01n就是系數(shù)向量a二(a,a，…,a)t的離散傅里葉變換.01n通過(guò)快速傅里葉變換(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+ax2h fax2, (3—2—3—1)0 2 4 n-1Ali](x)=a+ax+ax2f fax2? (3—2—3—2)1 3 5 n注意到Ab](x)包含A所有偶數(shù)下標(biāo)的系數(shù)，Abl(x)包含A中所有奇數(shù)下標(biāo)的系數(shù)，于是有：A(x)=Abl(x2)+xA[i](x2). (3—2—3—3)所以，求A(x)在W0,W1,???,Wn處的值的問(wèn)題轉(zhuǎn)化為：nf1 nf1 nf1求次數(shù)為-的多項(xiàng)式A[0](x),A[i](x)在點(diǎn)(W0)2,(Wi)2,???,2 nf1 nf1(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)式A[0](x),A[1](x)在nF1個(gè)nF1次單位復(fù)數(shù)根處進(jìn)行求值?這些子問(wèn)題與原始問(wèn)題形式相同，但規(guī)模變?yōu)橐话?下面確定DFT過(guò)程的時(shí)間復(fù)雜度.注意到除了遞歸調(diào)用外，每次調(diào)用需要枚舉a=(a,a，…,a)T中所有元素，將a劃分為ab]={a,a，…a}、0 1 n 0 2 nat]={a,a,a，…,a},分別與多項(xiàng)式A[0](x),A[u(x)相對(duì)應(yīng).其時(shí)間復(fù)雜135 n-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寫(xiě)成矩陣乘積y=Va，其中n+1nDn+1y1

y2Dn+1D2n+1D2n+1D4Dn+1y1

y2Dn+1D2n+1D2n+1D4n+1Dnn+1D2nn+1(a)0a1a2(3-3-1-1)CDnn+1D2nn+1Dn2丿n+1易知Vp0.即V可逆.n+1n+1F面證明V-1(i,j)處元素vn+1ijD-ij n11.n+1(3-3-1-2)考慮V-1V(i,j)處元素p:n+1 n+1 ijED-ED-ik+1 kjijn+1 n+1k-0EDk(j-i)—n+1——n+1k-0(3-3-1-3)當(dāng)j二當(dāng)j二i時(shí),p二1；當(dāng)j豐i時(shí)，根據(jù)(2-2-1-d)可知,p二0.ijij滿足V-滿足V-1Vn+1n+1 n(3-3-1-4)給定逆矩陣V-1,可以求出a-(a,a，…,a)T.n+1 01n(3-3-1-5)其中a-—1—￡yd-ki.(3-3-1-5)in+1 kn+1k-0(2)利用FFT計(jì)算逆DFT比較(3-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ù)通過(guò)加入n個(gè)系數(shù)為0的高階項(xiàng)，把多項(xiàng)式A(x)和B(x)變?yōu)榇螖?shù)為2n的多項(xiàng)式，并構(gòu)造其系數(shù)表達(dá).2、求值通過(guò)應(yīng)用2(n+1)階的FFT計(jì)算出A(x)和B(x)長(zhǎng)度為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è)表示中包含了C(x)在每個(gè)2(n+1)次單位根處的值.4、 插值通過(guò)對(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(log°pJog。q).當(dāng)p,q規(guī)模巨大時(shí),這種算法將會(huì)十分低效.因此，我們采取快速傅里葉變換進(jìn)行優(yōu)化.TOC\o"1-5"\h\z\o"CurrentDocument"設(shè)p二a-10n+a?10n-i+—fa?10i+a，其中0<a<9,aeN,0<i<n,ieNn n-1 1 0 ii(5-1)q二b?10m+b?10m-i+…+b?10i+b，其中0<b<9,beN,0<i<m,ieNm m-1 1 0 i i(5-2)令多項(xiàng)式A(x)二axnfaxn-1f—fax1fa， (5-3)n n-1 1 0B(x)二bxmfbxm-1f—fbx1fb. (5-4)m m-1 1 0(5-5)C(x)二A(x)B(x).(5-5)注意到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ù)》(第二版),高等教育出版