快速演算法

算法优化，最主要的目的是用來減少運算時間，像是加法、乘法的數目，以及所花的運算週期。此外還能降低硬體實現所花費的成本，像是減少緩衝器的數量、重複利用相同的硬體架構。

概覽

一般來說，快速演算法的設計可以透過將運算展開，並進行歸納、分析，利用运算次数更少的乘法、除法（如乘以二、除以二等左移、右移）來完成運算，達到降低運算時間的目的。

而在設計的過程中，因為乘法的運算時間會遠大於加法，因此通常會以使用多少個乘法來衡量整體的運算時間。此外，因為是從硬體的角度來看，所以對於乘上$2^{\pm k}$、0，都可以視為不需要任何的運算時間(trivial multiplications)，因為對於乘上$2^k$，或者除上$2^k$，分別只要進行左移$k$位元或右移$k$位元的運算即可達成。

簡單矩陣有关的算法优化設計

以下举几个例子，用以说明如何优化算法，使得矩阵演算能够最优化。 1.$y[1]=ax[1]+2ax[2]=\left[\begin{array}{cc}a& 2a\end{array}\right]\left[\begin{array}{c}x[1]\\ x[2]\end{array}\right]=a(x[1]+2x[2])$

從上面這個式子來看，在左邊的部分需要用到兩個乘法、一個加法，然而經過一些化簡、合併，在右邊的地方就只需要一個乘法(乘2不需要運算時間)、一個加法。

2.$\left[\begin{array}{c}y(1)\\ y(2)\end{array}\right]=\left[\begin{array}{cc}a& a\\ a& a\end{array}\right]\left[\begin{array}{c}x(1)\\ x(2)\end{array}\right]$

$y(2)=y(1)=a(x(1)+x(2))$，因此從原本需要四個乘法、兩個加法，變成只要一個乘法、一個加法。

3.$\left[\begin{array}{c}y(1)\\ y(2)\end{array}\right]=\left[\begin{array}{cc}a& -a\\ -a& a\end{array}\right]\left[\begin{array}{c}x(1)\\ x(2)\end{array}\right]$

$y(2)=-y(1),y(1)=a(x(1)-x(2))$，因此從原本的四個乘法、兩個加法，變成只需要一個乘法、二個加法。

4.$\left[\begin{array}{c}y(1)\\ y(2)\end{array}\right]=\left[\begin{array}{cc}a& b\\ b& a\end{array}\right]\left[\begin{array}{c}x(1)\\ x(2)\end{array}\right]$

$\left[\begin{array}{cc}a& b\\ b& a\end{array}\right]=\frac{1}{2}\left[\begin{array}{cc}a+b& a+b\\ a+b& a+b\end{array}\right]+\frac{1}{2}\left[\begin{array}{cc}a-b& b-a\\ b-a& a-b\end{array}\right]$, 左邊的部分可以參考例子2，右邊則是例子3，因此從原本的四個乘法、兩個加法，變成兩個乘法、四個加法。

5.$\left[\begin{array}{c}y(1)\\ y(2)\end{array}\right]=\left[\begin{array}{cc}a& b\\ c& a\end{array}\right]\left[\begin{array}{c}x(1)\\ x(2)\end{array}\right]$

$\left[\begin{array}{cc}a& b\\ c& a\end{array}\right]\left[\begin{array}{c}x(1)\\ x(2)\end{array}\right]=\left[\begin{array}{cc}a& a\\ a& a\end{array}\right]\left[\begin{array}{c}x(1)\\ x(2)\end{array}\right]+\left[\begin{array}{cc}0& b-a\\ c-a& 0\end{array}\right]\left[\begin{array}{c}x(1)\\ x(2)\end{array}\right]$

左邊的部分一樣可以參考例子2，所以需要一個乘法、一個加法，右邊的部分則需要兩個乘法，最後要將左右兩式相加，因此還需要兩個加法才能得到$\left[\begin{array}{c}y(1)\\ y(2)\end{array}\right]$，所以一共需要三個乘法、三個加法。

實際應用

一般來說，做傅立葉轉換會用到複數的乘法，會比一般實數的乘法多上四倍，若是利用快速演算法，則可以化簡如下：

$(a+bj)(c+dj)=ac-bd+j(ad+bd)=e+jf$

$\left[\begin{array}{c}e\\ f\end{array}\right]=\left[\begin{array}{cc}c& -d\\ d& c\end{array}\right]\left[\begin{array}{c}a\\ b\end{array}\right]=\left[\begin{array}{cc}c& c\\ c& c\end{array}\right]\left[\begin{array}{c}a\\ b\end{array}\right]+\left[\begin{array}{cc}0& -c-d\\ d-c& 0\end{array}\right]\left[\begin{array}{c}a\\ b\end{array}\right]$

因此左邊的部分可以參考例子2，所以需要一個乘法，右邊的部分則需要兩個乘法，因此可以由四個乘法變為三個乘法。

另外舉一個DFT的例子，一般來說DFT會需要$4N^2$個實數乘法：

$X[m]={\sum }_{n=0}^{N-1}x[n]e^{-j\frac{2\pi mn}{N}},N=3$

$\left[\begin{array}{ccc}1& 1& 1\\ 1& -1/2& -1/2\\ 1& -1/2& -1/2\end{array}\right]+j\left[\begin{array}{ccc}0& 0& 0\\ 0& -\sqrt{3}/2& \sqrt{3}/2\\ 0& \sqrt{3}/2& -\sqrt{3}/2\end{array}\right]$，左邊都是一些trivial multiplication，所以不需要乘法運算，右邊則可以參考例子3，所以需要一個乘法。整個DFT的運算可以由下式表示：

$X=Fx=(F_R+j{F}_I)(x_R+j{x}_I)=F_R{x}_R+j{F}_R{x}_I+j{F}_I{x}_R-F_I{x}_I$

所以最後一供需要$2*(0+1)=2$個乘法。

參考資料

-{R|http://djj.ee.ntu.edu.tw/ADSP10.pdf}-