На симпозиуме по дискретным алгоритмам ACM на этой неделе группа исследователей из MIT представила новый алгоритм быстрого преобразования Фурье sFFT (Sparse Fast Fourier Transform), который на некоторых задачах может быть в десятки или сотни раз быстрее классического БПФ.
Преобразование Фурье предполагает получение коэффициентов («амплитуд») при разложении исходной функции на элементарные составляющие — гармонические колебания с разными частотами. Быстрое преобразование Фурье позволяет ускорить этот процесс за счёт разделения вектора коэффициентов на два вектора, рекурсивном вычислении ДПФ для них, и объединении результатов в одно БПФ. Считается, что метод БПФ предложен в 1805 году Гауссом и переоткрыт в 1965 году, после чего нашёл широкое применение с распространением современных компьютеров. В последние 50 лет предпринималось немало попыток повысить эффективность БПФ, например, FFTW.
Новый алгоритм MIT, как заявляется, работает быстрее FFTW. Сравнение приводится в научной работе, а также на странице проекта.
Алгоритм sFFT (Sparse Fast Fourier Transform) создан на основе двух существующих фильтров (фильтр Гаусса и фильтр Чебышева) и нацелен на то, чтобы быстро найти фрагменты с «разреженным» сигналом (sparse signal) и определить исходную амплитуду в каждом из них. Сигнал разбивается на фрагменты (rapid sampling) до тех пор, пока не останется разреженный сигнал с единственной амплитудой. А уже там новый алгоритм выявляет её в 10 тыс. раз быстрее классического БПФ.
Такой метод не является универсальным, и сейчас учёные пытаются определить, в каких конкретно приложениях он даст наибольшую прибавку в производительности.
via MIT
