• Welcome to the world's largest Chinese hacker forum

    Welcome to the world's largest Chinese hacker forum, our forum registration is open! You can now register for technical communication with us, this is a free and open to the world of the BBS, we founded the purpose for the study of network security, please don't release business of black/grey, or on the BBS posts, to seek help hacker if violations, we will permanently frozen your IP and account, thank you for your cooperation. Hacker attack and defense cracking or network Security

    business please click here: Creation Security  From CNHACKTEAM

Recommended Posts

FFT 的若干优化

FFT计算优化的起点一般是充分利用虚部空间.因为没有优化计算,通常只有实部给出最终结果;而如果能利用好虚部,理论上最多能把FFT计算——减少一半左右,从“一次一个”减少到“两次一个”。

「三次」变「两次」

这种优化通常用于简单的多项式乘法。

如果我们要计算一个像\(F(x)G(x)\)这样的卷积,常用的方法是通过FFT计算\(\operatorname{DFT}(F)\)和\(\operatorname{DFT}(G)\),然后计算\ (\ operator name {id

为了实现我们之前的想法,我们尝试将\(\operatorname{DFT}(F)\)和\(\operatorname{DFT}(G)\)填充到FFT中。这还是比较简单的,只需要构造:

\[H(x)=F(x) iG(x)

\]

为了得到\(F(x)G(x)\),我们不难想到计算\ (h 2 (x) \):

\[H(x)=F^2(x)-G^2(x) i(2F(x)G(x))

\]

因此,通过提取\ (h 2 (x) \)的虚部,可以得到想要的结果。而且是两次FFT!

需要注意的是,对精度的要求是很高的,如果系数稍微大一点,还是少用这个优化比较好。

不可能,这就是FFT的问题。

「七次」变「四次」

这种优化常用于分裂系数FFT,即MTT。

考虑一个相对简单的情况:我们只需要把系数拆解一次,再乘以一次,也就是说,我们需要问:

\[(T \ cdot A(x)B(x))(T \ cdot C(x)D(x))

\]

其中\(T\)是常数,我们就当它比较小吧。

所以,我们直接拆开来说,就是问:

\[t^2\cdot a(x)c(x)t(a(x)d(x)b(x)c(x))b(x)d(x)

\]

大致,哇,要7次FFT!结束了!

还是用以前的思路,我们把两个多项式合二为一,比如:

\[P(x)=A(x) iB(x)\\

Q(x)=C(x) iD(x)

\]

你仍然可以尝试乘法:

\[PQ=AC-BD i(AD BC)

\]

我们最终的目标应该是试图找到\(AC,BD,AD BC\),也就是至少需要三个方程。但是,这里只提供了两个。

注意,每个方程都是两个变量相加和相减的形式。如果能多加几个同形式的方程,很有可能直接加减结果。调整符号直接找到共轭:

\[P\overline Q=AC BD i(-AD BC)

\]

这样我们甚至可以直接求解四个变量,只需要五次FFT,应该会快很多。

但是这还不够!\(Q\)和\(\overline Q\)之间变化不大。能否通过\(\ Operator Name { DFT }(\ overline Q)\)直接找到\(\operatorname{DFT}(Q)\)?

不能只是计算,但是FFT 的过程已经算好了 \(\omega_n^k\) 和 \(\overline{\omega_n^k}\) 两处的点值.我们尝试通过这个信息给出\(\ Operator Name { DFT }(\ overline q)\)。

考察两个复数\(Z1,z2 \)的运算;

\(\ overline { \ overline { z _ 1 } }=z _ 1 \).

\(\ overline { z _ 1 z _ 2 }=\ overline { z _ 1 } \ overline { z _ 2 } \).

\(\ overline { z _ 1 \ cdot z _ 2 }=\ overline { z _ 1 } \ cdot \ overline { z _ 2 } \).

因此可以得出\(q(\ omega _ n k)=\ outline { q(\ outline { \ omega _ n k })} \)。这个可以直接优化到第四个FFT!

另一种优化方法是直接获取\ (\操作符名称{DFT} (a),\操作符名称{DFT} (b),\操作符名称{DFT} (q) \)

这种方法的另一个关键是如何快速IDFT。类似于DFT的加速,我们也把两个需要IDFT的系数向量“塞进”同一个复数里。例如,您可以:

\[\ operator name { DFT }(F)=\ operator name { DFT }(AC)I \ operator name { DFT }(AD)

\]

有\(F=AC iAD\)。注意\(AC,AD\)的虚部为0,所以可以分别提取两部分得到结果。

小结

因此,优化FFT的关键在于:

压缩到同一个复数放两个数字以提高空间利用率。

利用共轭生成尽可能多的方程,的其他关系,求解所需变量。

Link to comment
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now