多項(xiàng)式乘法運(yùn)算

關(guān)于多項(xiàng)式乘法運(yùn)算第1頁，課件共30頁，創(chuàng)作于2023年2月引言

多項(xiàng)式是最基本的數(shù)學(xué)工具之一，由于其形式簡單，且易于用計(jì)算機(jī)對其進(jìn)行各種計(jì)算，在當(dāng)今的社會(huì)中應(yīng)用越來越廣。不僅在像Maple這樣的數(shù)學(xué)軟件中有著舉足輕重的作用，在工程、信息等諸多領(lǐng)域中都有著廣闊的應(yīng)用。

下面我們給出幾個(gè)多項(xiàng)式逼近的例子：第2頁，課件共30頁，創(chuàng)作于2023年2月多項(xiàng)式的基本運(yùn)算

加法運(yùn)算

求值運(yùn)算

乘法運(yùn)算第3頁，課件共30頁，創(chuàng)作于2023年2月普通的多項(xiàng)式乘法運(yùn)算

多項(xiàng)式乘法是一個(gè)很常見的問題，在通常的算法中，兩個(gè)次多項(xiàng)式的乘法需要用的時(shí)間才能完成。

讓我們先來看一看這樣的算法是如何進(jìn)行的：

第4頁，課件共30頁，創(chuàng)作于2023年2月...................................第5頁，課件共30頁，創(chuàng)作于2023年2月

在上面的過程中，似乎我們覺得這個(gè)算法并沒有做任何多余的事情，因?yàn)槲覀儽仨毧紤]每一組,它們的乘積對最終的結(jié)果都會(huì)產(chǎn)生影響。而且我們不能通過調(diào)整計(jì)算順序從根本上降低算法時(shí)間復(fù)雜度，至多只能使其常數(shù)因子稍小一些。

如果我們不能跳出以上思維的局限，我們就不可能在根本上降低算法的時(shí)間復(fù)雜度。

讓我們首先換一個(gè)角度來考察多項(xiàng)式。第6頁，課件共30頁，創(chuàng)作于2023年2月多項(xiàng)式的點(diǎn)值表示法

首先讓我們來看多項(xiàng)式的另一種表示方法：點(diǎn)值表示法,即用（其中，互不相同）來表示一個(gè)不超過次多項(xiàng)式。給定一個(gè)多項(xiàng)式，要給出n組點(diǎn)值對最簡單的方法是任選n個(gè)互不相同的xi，依次求出多項(xiàng)式在這n個(gè)點(diǎn)的值。用n個(gè)點(diǎn)值對也可以唯一確定一個(gè)不超過n-1次多項(xiàng)式，這個(gè)過程稱之為插值。第7頁，課件共30頁，創(chuàng)作于2023年2月引理1（多項(xiàng)式插值的唯一性）

對于任意n個(gè)點(diǎn)值對組成的集合,

其中互不相同，則存在唯一的次數(shù)不超過n-1的多項(xiàng)式，滿足continue第8頁，課件共30頁，創(chuàng)作于2023年2月存在性：已知不妨記為XA=YX是范德蒙矩陣，利用行列式的變換可得該矩陣的行列式的值為因此X有逆矩陣。第9頁，課件共30頁，創(chuàng)作于2023年2月唯一性：

若兩個(gè)函數(shù)次數(shù)不超過n-1次的多項(xiàng)式均符合題意，則多項(xiàng)式有n個(gè)根，且為不超過n-1次的多項(xiàng)式，所以,

即。back第10頁，課件共30頁，創(chuàng)作于2023年2月點(diǎn)值多項(xiàng)式的乘法

因此：適當(dāng)?shù)睦命c(diǎn)值表示可以使多項(xiàng)式的乘法可以在線性時(shí)間內(nèi)完成！第11頁，課件共30頁，創(chuàng)作于2023年2月

因?yàn)閒(x)g(x)的次數(shù)為n-1，r(x)的次數(shù)為2n-2,因此確定r(x)需要2n-1個(gè)點(diǎn)值對，而現(xiàn)在我們只有n個(gè)點(diǎn)值對。

我們可以通過對f(x)與g(x)的點(diǎn)值對個(gè)數(shù)的擴(kuò)充來解決這個(gè)問題，即將f(x),g(x）的點(diǎn)值對在一開始就取為2n-1。第12頁，課件共30頁，創(chuàng)作于2023年2月利用點(diǎn)值表示法改善多項(xiàng)式系數(shù)表示法的乘法

下面讓我們來看一看我們是否能夠利用點(diǎn)值表示法在計(jì)算多項(xiàng)式乘法時(shí)的線性時(shí)間來提高系數(shù)表示法的多項(xiàng)式乘法的速度。為了做到這一點(diǎn)，我們需要做：將多項(xiàng)式由系數(shù)表示法轉(zhuǎn)化為點(diǎn)值表示法(點(diǎn)值過程）利用點(diǎn)值表示法完成多項(xiàng)式乘法將點(diǎn)值表示法再轉(zhuǎn)化為系數(shù)表示法（插值過程）其中第二步只需要線性時(shí)間。問題的關(guān)鍵轉(zhuǎn)化為第一第三步。continue2continue1continue3第13頁，課件共30頁，創(chuàng)作于2023年2月1.由系數(shù)表示法轉(zhuǎn)化為點(diǎn)值表示法。（點(diǎn)值過程）

注意！x0,x1,…,xn-1是由我們自己選擇的，我們可以充分利用這一點(diǎn)通過適當(dāng)?shù)倪x擇使轉(zhuǎn)化過程降為O(nlogn)。

這里我們選擇1的n次單位根作為x0,x1,…,xn-1，即

其中第14頁，課件共30頁，創(chuàng)作于2023年2月引理2：對任何整數(shù)n>=0,k>=0,j>0,成立：證明：折半定理第15頁，課件共30頁，創(chuàng)作于2023年2月注意到，中包含了f中所有偶下標(biāo)的系數(shù)，而中包含了f中所有奇下標(biāo)的系數(shù)。并記求與在點(diǎn)的值。

問題：求設(shè)n為偶數(shù)（否則可以通過添加高次零項(xiàng)使n化為偶數(shù)）。第16頁，課件共30頁，創(chuàng)作于2023年2月另一方面，由折半定理：

并不是n個(gè)不同的數(shù)，而是僅由1的n/2次單位根組成，每個(gè)根恰好出現(xiàn)2次。

由此可以看到子問題與原問題形式相同，但規(guī)模縮小一半，這啟示我們可以利用分治的思想通過遞歸來解決這個(gè)問題。第17頁，課件共30頁，創(chuàng)作于2023年2月遞歸算法的具體實(shí)現(xiàn)過程遞歸邊界條件Functiontransform(a:atype):y:ytype；ifn=1thenreturna0遞歸預(yù)處理

ifodd(n)then

begininc(n);an-1:=0;end;遞歸過程Fork:=0ton-1do利用計(jì)算可以證明，以上計(jì)算方法的時(shí)間復(fù)雜度為O(nlogn)。back第18頁，課件共30頁，創(chuàng)作于2023年2月2．將點(diǎn)值表示法再轉(zhuǎn)化為系數(shù)表示法。（插值過程）

點(diǎn)值過程所解決的問題可以等效為一個(gè)矩陣方程：

插值過程是點(diǎn)值過程的逆運(yùn)算。這個(gè)問題比前一個(gè)問題看起來更復(fù)雜，但事實(shí)上，通過適當(dāng)?shù)霓D(zhuǎn)化可以把這個(gè)問題轉(zhuǎn)化為前一個(gè)問題。記為第19頁，課件共30頁，創(chuàng)作于2023年2月YA點(diǎn)值過程插值過程如果存在第20頁，課件共30頁，創(chuàng)作于2023年2月引理3第21頁，課件共30頁，創(chuàng)作于2023年2月利用引理3，我們就可以很容易的解決插值的問題。

YA可等效為矩陣方程：

因此，我們可以充分利用點(diǎn)值過程的方法求出多項(xiàng)式的系數(shù)表達(dá)。第22頁，課件共30頁，創(chuàng)作于2023年2月遞歸邊界條件Functiontransform(a:atype):y:ytype；ifn=1thenreturna0遞歸預(yù)處理

ifodd(n)then

begininc(n);an-1:=0;end;遞歸過程Fork:=0ton-1do利用計(jì)算backa:atypey:ytypey0yn-1:=0;遞歸結(jié)束后再將a中每一個(gè)數(shù)除以n。第23頁，課件共30頁，創(chuàng)作于2023年2月多項(xiàng)式乘法的算法流程

問題：f(x),g(x)是兩個(gè)n-1次的多項(xiàng)式，已知f(x)g(x)的系數(shù)表示，求出r(x)=f(x)*g(x)的系數(shù)表示。

算法流程：1.預(yù)處理：通過加入n-1個(gè)值為0的高價(jià)次數(shù)，使f(x)g(x)的次數(shù)增加到2n-2。這是為了使點(diǎn)值對的個(gè)數(shù)足夠能夠唯一確定r(x)。2.點(diǎn)值：利用分治的方法，通過函數(shù)transform求出f(x)與g(x)在1的2n-1次單位根處的值。3.點(diǎn)乘：將f(x),g(x)在各點(diǎn)的值逐點(diǎn)相乘，計(jì)算出r(x)在各點(diǎn)的值。

4.

插值：互換a與y的作用，再利用函數(shù)transform求r(x)的系數(shù)表示，并注意要將結(jié)果除以次數(shù)作為最后結(jié)果。以上第1、第3步的執(zhí)行時(shí)間都是O(n)，第2、第4步的執(zhí)行時(shí)間都是O(nlogn)。

第24頁，課件共30頁，創(chuàng)作于2023年2月算法改進(jìn)

在函數(shù)transform中，我們是用遞歸的方式來求解，我們對n=8的情況來具體演示一下遞歸調(diào)用的過程。第25頁，課件共30頁，創(chuàng)作于2023年2月

但是遞歸的方法對空間的要求很高，從函數(shù)transform中可以看到每次遞歸調(diào)用時(shí)都需要新的系數(shù)數(shù)組傳入遞歸過程內(nèi)部。而通過剛才的演示，我們發(fā)現(xiàn)我們也可以用從底向上迭代的方法來進(jìn)行。第26頁，課件共30頁，創(chuàng)作于2023年2月迭代算法的具體實(shí)現(xiàn)過程初始化預(yù)處理通過增加高次零項(xiàng)使將多項(xiàng)式的次數(shù)增加到2的冪次。Functiontransform_better(a:atype):y:ytype;y:=a;迭代過程Fork:=1tolgndo對數(shù)組進(jìn)行恰當(dāng)?shù)暮喜⒉⒔Y(jié)果放到數(shù)組恰當(dāng)?shù)奈恢?。?7頁，課件共30頁，創(chuàng)作于2023年2月yyyyback第28頁，課件共30頁，創(chuàng)作于2023年2月

下面我們將本文介紹的方法與普通的多項(xiàng)式乘法做一個(gè)比較。多項(xiàng)式次數(shù)n=100n=1000n=10000n=20000n=30