7 лет назад 27 января 2012 в 6:32 142

Новый алгоритм преобразование Фурье

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

Преобразование Фурье предполагает получение коэффициентов («амплитуд») при разложении исходной функции на элементарные составляющие — гармонические колебания с разными частотами. Быстрое преобразование Фурье позволяет ускорить этот процесс за счёт разделения вектора коэффициентов на два вектора, рекурсивном вычислении ДПФ для них, и объединении результатов в одно БПФ. Считается, что метод БПФ предложен в 1805 году Гауссом и переоткрыт в 1965 году, после чего нашёл широкое применение с распространением современных компьютеров. В последние 50 лет предпринималось немало попыток повысить эффективность БПФ, например, FFTW.

Новый алгоритм MIT, как заявляется, работает быстрее FFTW. Сравнение приводится в научной работе, а также на странице проекта.

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

Такой метод не является универсальным, и сейчас учёные пытаются определить, в каких конкретно приложениях он даст наибольшую прибавку в производительности.

Никто не прокомментировал материал. Есть мысли?