利用快速傅里葉變換(FFT)計算多項式乘法(共11頁)

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

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

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

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

5、果的點值表達形式(1)單位復(fù)數(shù)根次單位復(fù)數(shù)根是滿足的復(fù)數(shù).次單位復(fù)數(shù)根恰好有個:對于,這些根是.由Euler公式可知,這個單位復(fù)數(shù)根均勻地分布在以復(fù)平面原點為圓心的單位圓圓周上.稱為主次單位根,所有其他次單位根都是的冪次.個次單位復(fù)數(shù)根,.,在乘法意義下構(gòu)成一個群,該群與群同構(gòu).由此,可以得到如下推論: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)對于次多項式,其系數(shù)形式為.(3-2-2-1)設(shè),(3-2-2-2)則

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

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

8、3-3-1-1)易知.即可逆.下面證明處元素.(3-3-1-2)考慮處元素:.(3-3-1-3)當(dāng)時,;當(dāng)時,根據(jù)(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:把與互換,用替換,并且將計算結(jié)果每個元素除以.因此,我們也可以在時間內(nèi)計算出逆DFT.四、算法具體流程1、加倍多項式次數(shù)通過加入個系數(shù)為的高階項,把多項式和變?yōu)榇螖?shù)為的多項式,并構(gòu)造其系數(shù)表達.2、求值通過應(yīng)用階的FFT計算出和長度為的點值表達.這些點值表達中包含了兩

9、個多項式在次單位根處的取值.3、逐點相乘把的值與的值逐點相乘,可以計算出的點值表達,這個表示中包含了在每個次單位根處的值.4、插值通過對個點值應(yīng)用FFT,計算其逆DFT,就可以構(gòu)造出多項式的系數(shù)表達.由于1、3的時間復(fù)雜度為,2、4的時間復(fù)雜度為,因此整個算法的時間復(fù)雜度為.五、算法的實際應(yīng)用:計算大整數(shù)乘法在密碼學(xué)等領(lǐng)域中,經(jīng)常需要進行大整數(shù)乘法運算.如果對整數(shù)逐位相乘然后相加,其時間復(fù)雜度為.當(dāng)規(guī)模巨大時,這種算法將會十分低效.因此,我們采取快速傅里葉變換進行優(yōu)化.設(shè),其中(5-1) ,其中(5-2)令多項式,(5-3) .(5-4) .(5-5)注意到,.因此.(5-6)將大整數(shù)相乘轉(zhuǎn)化為多項式的乘法,應(yīng)用快速傅里葉變換,即可得出結(jié)果.6、 參考文獻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、