快速演算法設計的原則

快速演算法設計原理
*快速演算法的主要目標為節省計算時間，採取手段主要如下：
*#減少加法數量
*#減少乘法數量
*#減少迴圈數量
**其中以減少乘法數量最為重要，可以最為高效率節省計算量。

快速演算法的設計重要的四種概念
N-point DFT
對於任何點數的離散傅立葉轉換(DFT)，都有其適合的快速演算法．

線性非時變系統的運算複雜度
由於線性非時變系統可以用卷積Convolution來表示，故我們可以說其運算複雜度為，三個傅立葉轉換的計算量（包括兩個FTs 以及一個IFT)

⇒3 \theta(NlogN)

⇒ \theta(NlogN)

若使用了快速演算法，我們可以將其運算複雜度降為 \theta(N)

Replacement of DFTs
對於DFT的計算有複數(complex number)的問題，我們也可以透過矩陣的方式來處理．

運算簡化技巧
下面以四個例子來解說：

(1) y_1 = ax_1 + 2ax_2
⇒y_1=\begin{pmatrix} a & 2a \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}

⇒y_1 = a(x_1 + 2x_2)

⇒1 MULs, 1 ADD (一個乘法，一個加法)

(2)\begin{pmatrix} y_1 \\ y_2 \end{pmatrix} =\begin{pmatrix} a & a \\ a & a \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}

⇒y_1 = a(x_1 + x_2)

⇒y_2 = y1

⇒1 MULs, 1 ADD

(3)\begin{pmatrix} y_1 \\ y_2 \end{pmatrix} =\begin{pmatrix} a & b \\ b & a \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}

⇒\begin{pmatrix} y_1 \\ y_2 \end{pmatrix} =\begin{pmatrix} \frac{a+b}{2} & \frac{a+b}{2} \\ \frac{a+b}{2} & \frac{a+b}{2} \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}+ \begin{pmatrix} \frac{a-b}{2} & -\frac{a-b}{2} \\ -\frac{a-b}{2} & \frac{a-b}{2} \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}

⇒2MULs, 4 ADDs

(4)\begin{pmatrix} y_1 \\ y_2 \end{pmatrix} =\begin{pmatrix} a & b \\ c & a \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}

⇒\begin{pmatrix} y_1 \\ y_2 \end{pmatrix} =\begin{pmatrix} a & a \\ a & a \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}+ \begin{pmatrix} 0 & b-a \\ c-a & 0 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}

⇒3MULs, 3 ADDs

複數的乘法
if x = a + ib and y = c + id

⇒xy = ac-bd + i(ad+bc )

令e為實數項，f為虛數項

\begin{pmatrix} e \\ f \end{pmatrix} =\begin{pmatrix} c & -d \\ d & c \end{pmatrix} \begin{pmatrix} a \\ b \end{pmatrix} =\begin{pmatrix} c & c\\ c & c \end{pmatrix}\begin{pmatrix} a \\ b \end{pmatrix} + \begin{pmatrix} 0 & -c-d\\ d-c & 0 \end{pmatrix}\begin{pmatrix} a \\ b \end{pmatrix}

(1) let x_1 = c(a + b) ; y_1 = x_1

(2) let x_2 = (-c-d)b ; y_2 = (d-c)a

⇒e = x_1+x_2 ; f = y_1+y_2
⇒3MULs, 3～5 ADDs
從這裡我們可以看出虛數的乘法量大致為實數乘法量的三倍。

参考