sFFT — Sparse Fast Fourier Transform — новый алгоритм быстрого преобразования Фурье

В январе 2012 произошло одно интересное событие. На симпозиуме по дискретным алгоритмам ACM группа исследователей из MIT представила новый алгоритм быстрого преобразования Фурье(wiki) — sFFT (Sparse Fast Fourier Transform), способный на некоторых задачах быть в десятки или сотни раз быстрее классического быстрого преобразования Фурье (БПФ). sFFT: Sparse Fast Fourier Transform

По заявлению MIT, новый алгоритм работает быстрее FFTW.

Сравнение приводится в научной работе, а также на странице проекта.

Алгоритм sFFT (Sparse Fast Fourier Transform) создан на основе двух существующих фильтров (фильтр Гаусса и фильтр Чебышева) и нацелен на то, чтобы быстро найти фрагменты с «разреженным» сигналом (sparse signal) и определить исходную амплитуду в каждом из них. Сигнал разбивается на фрагменты (rapid sampling) до тех пор, пока не останется разреженный сигнал с единственной амплитудой. А новый алгоритм выявляет её в 10 тыс. раз быстрее классического БПФ.

Преобразование Фурье предполагает представление из временного представления сигнала в частотное представление и осуществляется это путем получение коэффициентов («амплитуд»). Таким образом, «смесь» нескольких сигналов можно представить как частотные выражения с собственными амплитудами. Делается операция БПФ путем разложения исходной функции на элементарные составляющие — гармонические колебания с разными частотами.

Быстрое преобразование Фурье позволяет ускорить этот процесс за счёт разделения вектора коэффициентов на два вектора, рекурсивном вычислении ДПФ для них, и объединении результатов в одно БПФ.

Метод БПФ предложен в 1805 году Гауссом и пере открыт в 1965 году, после чего нашёл широкое применение с распространением современных компьютеров. В последние 50 лет было немало попыток повысить эффективность БПФ, например, FFTW.

Один комментарий

Добавить комментарий