傅里叶级数求和的快速方法？

Question

我已经使用FFTW生成了系数，现在我想重建原始数据，但只使用第一个numCoefs系数，而不是所有的系数。目前我使用的是下面的代码，它非常慢：

for ( unsigned int i = 0; i < length; ++i )
{
    double sum = 0;
    for ( unsigned int j = 0; j < numCoefs; ++j )
    {
        sum += ( coefs[j][0] * cos( j * omega * i ) ) + ( coefs[j][1] * sin( j * omega * i ) );
    }
    data[i] = sum;
}

有没有更快的方法？

Answer 1

一种更简单的解决方案是将不需要的系数置零，然后用FFTW进行IFFT。这将比做上面的IDFT高效得多。

请注意，当您这样做时，您可能会在时域中得到一些伪影-您实际上是在频域中乘以阶跃函数，这相当于在时域中使用sinc函数进行卷积。为了减少在时域中产生的“振铃”，你应该使用窗口函数来平滑非零系数和零系数之间的过渡。

Answer 2

如果您的长度接近或大于log( numCoefs )，那么计算复杂度为O(n*log(n))的IFFT很可能会更快，而且会为您预先优化。除了你想保留的系数外，只需将所有的柱子置零，如果你想要一个真实的结果，请确保也保留它们的负频率复数共轭。

如果您的对数相对于numCoefs (长度)很小，那么您可以尝试的其他优化方法包括:如果您实际上不需要超过6位数的精度，则可以使用sinf()和cosf()，以及在内部循环之外预先计算omega*i (尽管您的编译器应该为您做这件事，除非您的优化设置为低或关闭)。