快速演算法

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

概覽

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

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

簡單矩陣有關的算法優化設計

以下舉幾個例子，用以說明如何優化算法，使得矩陣演算能夠最優化。 1.$y[1]=ax[1]+2ax[2]={\begin{bmatrix}a&2a\end{bmatrix}}{\begin{bmatrix}x[1]\\x[2]\end{bmatrix}}=a(x[1]+2x[2])$

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

2.${\begin{bmatrix}y(1)\\y(2)\end{bmatrix}}={\begin{bmatrix}a&a\\a&a\end{bmatrix}}{\begin{bmatrix}x(1)\\x(2)\end{bmatrix}}$

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

3.${\begin{bmatrix}y(1)\\y(2)\end{bmatrix}}={\begin{bmatrix}a&-a\\-a&a\end{bmatrix}}{\begin{bmatrix}x(1)\\x(2)\end{bmatrix}}$

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

4.${\begin{bmatrix}y(1)\\y(2)\end{bmatrix}}={\begin{bmatrix}a&b\\b&a\end{bmatrix}}{\begin{bmatrix}x(1)\\x(2)\end{bmatrix}}$

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

5.${\begin{bmatrix}y(1)\\y(2)\end{bmatrix}}={\begin{bmatrix}a&b\\c&a\end{bmatrix}}{\begin{bmatrix}x(1)\\x(2)\end{bmatrix}}$

${\begin{bmatrix}a&b\\c&a\end{bmatrix}}{\begin{bmatrix}x(1)\\x(2)\end{bmatrix}}={\begin{bmatrix}a&a\\a&a\end{bmatrix}}{\begin{bmatrix}x(1)\\x(2)\end{bmatrix}}+{\begin{bmatrix}0&b-a\\c-a&0\end{bmatrix}}{\begin{bmatrix}x(1)\\x(2)\end{bmatrix}}$

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

實際應用

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

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

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

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

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

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

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

$X=Fx=(F_{R}+jF_{I})(x_{R}+jx_{I})=F_{R}x_{R}+jF_{R}x_{I}+jF_{I}x_{R}-F_{I}x_{I}$

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

參考資料

http://djj.ee.ntu.edu.tw/ADSP10.pdf