Быстрый способ суммировать ряды Фурье?

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

Гораздо более простым решением было бы обнулить нежелательные коэффициенты, а затем выполнить IFFT с FFTW.Это будет намного эффективнее, чем выполнение IDFT, как описано выше.

Обратите внимание, что при выполнении подобных действий вы можете получить некоторые артефакты во временной области - вы эффективно умножаетесь на шагфункция в частотной области, которая эквивалентна свертке с функцией sinc во временной области.Для уменьшения результирующего «звонка» во временной области следует использовать оконную функцию, чтобы сгладить переход между ненулевым и нулевым коэффициентами.

Answer 2

Если ваш numCoefs где-то ближе или больше, чем log (длина), то IFFT, который по сложности вычислений равен O (n * log (n)), скорее всего будет быстрее, а также предварительно оптимизирован для тебя. Просто обнулите все ячейки, кроме тех коэффициентов, которые вы хотите сохранить, и убедитесь, что также сохраните их комплексные сопряженные с отрицательной частотой, если вы хотите получить реальный результат.

Если ваша numCoefs мала по сравнению с log (length), тогда вы можете попробовать другие оптимизации, используя sinf() и cosf(), если вам не нужно больше 6 цифр точности, и предварительный расчет omega * i вне внутреннего цикла (хотя ваш компилятор должен делать это за вас, если у вас не задан низкий или низкий уровень оптимизации).