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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上利用快速傅里葉變換(FFT)計(jì)算多項(xiàng)式乘法作者:宋振華摘要本文將討論快速傅里葉變換(FFT),利用FFT設(shè)計(jì)一種算法,使多項(xiàng)式相乘的時(shí)間復(fù)雜度降低為,以便在計(jì)算機(jī)上高效計(jì)算多項(xiàng)式乘法.關(guān)鍵詞:快速傅里葉變換、多項(xiàng)式乘法目錄1、 引言2、 算法概述三、引理1、多項(xiàng)式的表示(1)系數(shù)表達(dá)形式(2)點(diǎn)值表達(dá)形式(3)插值2、利用離散傅里葉變換(DFT)與FFT導(dǎo)出結(jié)果的點(diǎn)值表達(dá)形式(1)單位復(fù)數(shù)根(2)離散傅里葉變換(DFT)(3)通過快速傅里葉變換(FFT)計(jì)算向量3、 利用FFT計(jì)算逆DFT,將結(jié)果的點(diǎn)值表達(dá)形式化為系數(shù)表達(dá)形式(1)在單位復(fù)數(shù)根處插值(2)利用FFT計(jì)

2、算逆DFT四、算法具體流程五、算法的實(shí)際應(yīng)用:計(jì)算大整數(shù)乘法六、參考文獻(xiàn)1、 引言基于FFT的離散傅里葉變換(DFT)技術(shù),是當(dāng)今信息傳輸、頻譜分析等領(lǐng)域中最重要的數(shù)學(xué)工具之一.在計(jì)算機(jī)編程中,我們經(jīng)常需要計(jì)算兩個(gè)多項(xiàng)式函數(shù)的乘積.對(duì)于兩個(gè)次多項(xiàng)式函數(shù),計(jì)算其乘積最直接方法所需時(shí)間為.本文將討論快速傅里葉變換(FFT),利用FFT設(shè)計(jì)一種算法,使多項(xiàng)式相乘的時(shí)間復(fù)雜度降低為,以便在計(jì)算機(jī)上高效執(zhí)行.2、 算法概述通過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á)形式

3、.3、 引理1、 多項(xiàng)式的表示(1)系數(shù)表達(dá)對(duì)于次數(shù)為的多項(xiàng)式,其系數(shù)表達(dá)是一個(gè)由系數(shù)組成的向量.考慮用系數(shù)形式表示、次數(shù)為的多項(xiàng)式、的乘法運(yùn)算.記.有.可以看出,采取逐個(gè)計(jì)算的方式進(jìn)行求解,其時(shí)間復(fù)雜度為.(2)點(diǎn)值表達(dá)a.定義:一個(gè)次數(shù)為的多項(xiàng)式的點(diǎn)值表達(dá)就是由一個(gè)有個(gè)點(diǎn)值對(duì)組成的集合,使得對(duì)于,所有的各不相同.b.點(diǎn)值表達(dá)下多項(xiàng)式乘法對(duì)于次多項(xiàng)式,設(shè)其點(diǎn)值表達(dá)式分別為:,:設(shè),由于的次數(shù)為,因此必須對(duì)和的點(diǎn)值表達(dá)式進(jìn)行擴(kuò)展,使每個(gè)多項(xiàng)式都包含個(gè)點(diǎn)值對(duì).給定,的擴(kuò)展點(diǎn)值表達(dá):,:.則的點(diǎn)值表達(dá)形式為:.因此,計(jì)算點(diǎn)值表達(dá)式的時(shí)間復(fù)雜度為.(3)插值 求值運(yùn)算的逆(從一個(gè)多項(xiàng)式的點(diǎn)值表達(dá)形式

4、確定其系數(shù)表達(dá)形式)稱為插值.下面將證明,個(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à)于矩陣方程:=.(3-1-3-a)記系數(shù)矩陣為,由Vandermonde行列式可知,.而,有,因此,即可逆.因此對(duì)于給定點(diǎn)值表達(dá),我們能夠唯一確定系數(shù)表達(dá)式,且.b.對(duì)于次數(shù)為的多項(xiàng)式函數(shù),插值算法基于如下Lagrange公式:.(3-1-3-b)容易驗(yàn)證,Lagrange公式的計(jì)算復(fù)雜度為.因此,個(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é)

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

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

7、我們遞歸地對(duì)次數(shù)為的多項(xiàng)式,在個(gè)次單位復(fù)數(shù)根處進(jìn)行求值.這些子問題與原始問題形式相同,但規(guī)模變?yōu)橐话?下面確定DFT過程的時(shí)間復(fù)雜度.注意到除了遞歸調(diào)用外,每次調(diào)用需要枚舉中所有元素,將劃分為、,分別與多項(xiàng)式,相對(duì)應(yīng).其時(shí)間復(fù)雜度為.因此,對(duì)運(yùn)行時(shí)間有下列遞推式:.(3-2-3-4)求解該遞推式,有.(3-2-3-5)采取快速傅里葉變換,我們可以在時(shí)間內(nèi),求出次數(shù)為的多項(xiàng)式在次單位復(fù)數(shù)根處的值.3、 利用FFT計(jì)算逆DFT將結(jié)果的點(diǎn)值表達(dá)形式化為系數(shù)表達(dá)形式(1)在單位復(fù)數(shù)根處插值根據(jù)(2-1-3-a),我們可以把DFT寫成矩陣乘積,其中是一個(gè)由適當(dāng)冪次填充成的Vandermonde矩陣.=(

8、3-3-1-1)易知.即可逆.下面證明處元素.(3-3-1-2)考慮處元素:.(3-3-1-3)當(dāng)時(shí),;當(dāng)時(shí),根據(jù)(2-2-1-d)可知,.滿足.(3-3-1-4)給定逆矩陣,可以求出.其中.(3-3-1-5)(2)利用FFT計(jì)算逆DFT比較(3-3-1-5)和(3-2-2-2)可知,對(duì)FFT算法進(jìn)行如下修改,即可計(jì)算出逆DFT:把與互換,用替換,并且將計(jì)算結(jié)果每個(gè)元素除以.因此,我們也可以在時(shí)間內(nèi)計(jì)算出逆DFT.四、算法具體流程1、加倍多項(xiàng)式次數(shù)通過加入個(gè)系數(shù)為的高階項(xiàng),把多項(xiàng)式和變?yōu)榇螖?shù)為的多項(xiàng)式,并構(gòu)造其系數(shù)表達(dá).2、求值通過應(yīng)用階的FFT計(jì)算出和長(zhǎng)度為的點(diǎn)值表達(dá).這些點(diǎn)值表達(dá)中包含了兩

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