利用快速傅里葉變換計算多項式乘法第一頁，共四十一頁，編輯于2023年，星期五問題引入：整數(shù)乘法1.n位數(shù)與1位數(shù)相乘78125×8000526逐位相乘乘法計算次數(shù)=n位數(shù)的位數(shù)時間復雜度第二頁，共四十一頁，編輯于2023年，星期五問題引入：整數(shù)乘法2.n位數(shù)與n位數(shù)相乘78125×16384312500625000234375468750128000000078125(2)中每一位同(1)逐位相乘(1)(2)乘法計算次數(shù)n項2n位(最多)加法計算次數(shù)總計算次數(shù)時間復雜度第三頁，共四十一頁，編輯于2023年，星期五問題引入：整數(shù)乘法兩個n位數(shù)相乘的時間復雜度為當n非常大時(如n>10000時)，利用計算機直接計算兩個n位數(shù)的乘積將十分低效。為了高效進行大整數(shù)乘法，需要一種更高效的算法。利用快速傅里葉變換計算n位大整數(shù)乘法，其時間復雜度為第四頁，共四十一頁，編輯于2023年，星期五一、多項式的兩種表達形式1、系數(shù)表達多項式：其系數(shù)為：將系數(shù)寫為向量形式：系數(shù)向量稱為多項式的系數(shù)表達形式。第五頁，共四十一頁，編輯于2023年，星期五兩個n次多項式的加法(1)(2)＋(3)其中，，,...,第六頁，共四十一頁，編輯于2023年，星期五系數(shù)表達下兩個n次多項式的加法的系數(shù)向量的系數(shù)向量的系數(shù)向量n+1次加法運算時間復雜度：第七頁，共四十一頁，編輯于2023年，星期五系數(shù)表達式下兩個n次多項式的乘法的系數(shù)向量的系數(shù)向量令將與中的系數(shù)兩兩相乘。其時間復雜度為計算C(x)系數(shù)第八頁，共四十一頁，編輯于2023年，星期五2、點值表達對于n次多項式任取n+1個不同的點第九頁，共四十一頁，編輯于2023年，星期五根據(jù)n+1個點唯一確定n次多項式系數(shù):未知量:已知量n+1元一次方程組第十頁，共四十一頁，編輯于2023年，星期五矩陣形式的方程組=系數(shù)矩陣行列式不為0證明方程具有唯一解只需證明第十一頁，共四十一頁，編輯于2023年，星期五證明系數(shù)矩陣行列式不為0=由于當時，必有，所以≠矩陣滿秩因此，方程組具有唯一解。Vandermonde行列式第十二頁，共四十一頁，編輯于2023年，星期五點值表達任取n+1個不同的點，可確定唯一n次多項式。換句話說，對于：可以作為n次多項式的一種表述形式。點值表達：第十三頁，共四十一頁，編輯于2023年，星期五點值表達下n次多項式,的加法：：的點值表達為：：注意A(x),B(x)在相同的n+1個位置取值點值表達為：時間復雜度為第十四頁，共四十一頁，編輯于2023年，星期五需要將A(x),B(x)點值表達擴展到2n+1對：：點值表達下n次多項式的乘法點值表達為：可以得到C(x)中n+1對點值：而C(x)是2n次多項式表示C(x)第十五頁，共四十一頁，編輯于2023年，星期五：：點值表達下n次多項式的乘法擴展點值表達為：可以得到C(x)點值表達：時間復雜度為2n+1次乘法運算第十六頁，共四十一頁，編輯于2023年，星期五系數(shù)表達與點值表達是等價的系數(shù)表達：點值表達：求值插值拉格朗日插值公式定義完備，互逆運算第十七頁，共四十一頁，編輯于2023年，星期五系數(shù)表達與點值表達比較及轉(zhuǎn)換系數(shù)表達點值表達求值插值普通乘法時間點值乘法時間時間時間假設存在第十八頁，共四十一頁，編輯于2023年，星期五一種快速計算多項式乘法的算法(系數(shù)表示)1、對A,B進行求值，時間復雜度算法描述：在上述假設下，求值與插值時間復雜度均為2、對A,B進行點值乘法，時間復雜度3、對結(jié)果進行插值，時間復雜度A,B為多項式的系數(shù)表達形式假設確實成立,借助FFT能夠?qū)崿F(xiàn)第十九頁，共四十一頁，編輯于2023年，星期五二、快速求值求值時間若任取2n+1個點直接求值，計算所需時間:計算加法所需時間:在每一個點處求值時間對所有點求值時間:需要降為:第二十頁，共四十一頁，編輯于2023年，星期五二、快速求值求值時間適當選取2n+1個點與算法，每個點求值時間可以降為:對所有點求值時間將為:特殊取值：2n+1次單位復數(shù)根第二十一頁，共四十一頁，編輯于2023年，星期五單位復數(shù)根定義：n次單位復數(shù)根是滿足的復數(shù).n次單位復數(shù)根恰好有n個求解由歐拉公式知,第二十二頁，共四十一頁，編輯于2023年，星期五單位復數(shù)根主n次單位根：n次單位復數(shù)根幾何意義k=1左圖為8次單位根在復平面上的分布。n次單位根在復平面上均勻分布其他n次單位根都是的冪次0(8)1345726第二十三頁，共四十一頁，編輯于2023年，星期五單位復數(shù)根的性質(zhì)n個n次單位復數(shù)根乘法意義下構(gòu)成群：在乘法意義下構(gòu)成群。該群與群(整數(shù)模n)同構(gòu)，即第二十四頁，共四十一頁，編輯于2023年，星期五單位復數(shù)根的性質(zhì)消去引理：對于偶數(shù)n>0：第二十五頁，共四十一頁，編輯于2023年，星期五單位復數(shù)根的性質(zhì)折半引理：n為偶數(shù)n個n次單位復數(shù)根的平方的集合，就是n/2個n/2次單位復數(shù)根的集合。第二十六頁，共四十一頁，編輯于2023年，星期五單位復數(shù)根的性質(zhì)折半引理的幾何意義：8次單位復數(shù)根在復平面上的分布0(8)1234567第二十七頁，共四十一頁，編輯于2023年，星期五單位復數(shù)根的性質(zhì)折半引理的證明：由消去引理知：此時又有第二十八頁，共四十一頁，編輯于2023年，星期五單位復數(shù)根的性質(zhì)求和引理：k是非負整數(shù)，k不是n的倍數(shù)求和引理證明：====0k不是n的倍數(shù)，第二十九頁，共四十一頁，編輯于2023年，星期五離散傅里葉變換(DFT)回顧我們希望計算在處的值（即在n+1個n+1次單位根處）假設A以系數(shù)形式給出，系數(shù)向量第三十頁，共四十一頁，編輯于2023年，星期五離散傅里葉變換(DFT)定義結(jié)果：就是系數(shù)向量的離散傅里葉變換采用普通乘法進行計算，時間復雜度為第三十一頁，共四十一頁，編輯于2023年，星期五離散傅里葉變換與快速傅里葉變換(FFT)有必要利用單位復數(shù)根的特殊性質(zhì)，降低時間復雜度引入快速傅里葉變換計算離散傅里葉變換第三十二頁，共四十一頁，編輯于2023年，星期五離散傅里葉變換與快速傅里葉變換(FFT)對于n次多項式：此處假設n+1是2的整數(shù)次冪偶數(shù)下標奇數(shù)下標第三十三頁，共四十一頁，編輯于2023年，星期五離散傅里葉變換與快速傅里葉變換(FFT)對于求A(x)在,,...,處取值轉(zhuǎn)化為：求(n-1)/2次多項式,在,,處取值處取值即,,...,折半引理然后將結(jié)果相加得到A(x)第三十四頁，共四十一頁，編輯于2023年，星期五離散傅里葉變換與快速傅里葉變換(FFT)遞歸地處理分解成兩個相似的子問題，規(guī)模減半拆分時,需要把n+1個系數(shù)拆成兩部分.時間復雜度FFT第三十五頁，共四十一頁，編輯于2023年，星期五離散傅里葉變換與快速傅里葉變換(FFT)時間復雜度遞推公式規(guī)模為n的時間復雜度拆分成2個n/2規(guī)模的子問題拆分問題代價求解該遞推式，有采用FFT,可以在時間內(nèi)實現(xiàn)插值第三十六頁，共四十一頁，編輯于2023年，星期五插值時間利用快速傅里葉變換實現(xiàn)插值回顧不妨先考慮n次多項式A(x)的插值依然假設n+1是2的整數(shù)次冪第三十七頁，共四十一頁，編輯于2023年，星期五利用快速傅里葉變換實現(xiàn)插值離散傅里葉變換中的一項：將離散傅里葉變換寫成矩陣形式：=易知：可逆未知量第三十八頁，共四十一頁，編輯于2023年，星期五利用快速傅里葉變換實現(xiàn)插值下面證明：處元素考慮：處元素當時：當時