快速算法

算法优化，最主要的目的是用来减少运算时间，像是加法、乘法的数目，以及所花的运算周期。此外还能降低硬件实现所花费的成本，像是减少缓冲器的数量、重复利用相同的硬件架构。

概览

一般来说，快速算法的设计可以透过将运算展开，并进行归纳、分析，利用运算次数更少的乘法、除法（如乘以二、除以二等左移、右移）来完成运算，达到降低运算时间的目的。

而在设计的过程中，因为乘法的运算时间会远大于加法，因此通常会以使用多少个乘法来衡量整体的运算时间。此外，因为是从硬件的角度来看，所以对于乘上$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