快速演算法設計的原則

快速演算法設計原理

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

快速演算法的設計重要的四種概念

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 從這裡我們可以看出虛數的乘法量大致為實數乘法量的三倍。