快速算法设计的原则

快速算法设计原理

• 快速算法的主要目标为节省计算时间，采取手段主要如下：
  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 从这里我们可以看出虚数的乘法量大致为实数乘法量的三倍。