Математики МТИ на порядок ускорили алгоритм быстрого преобразования Фурье

Источник: MIT

Исследователи из Массачусетского технологического института объявили о разработке алгоритма быстрого вычисления дискретного преобразования Фурье, на определенных задачах работающего в десять раз быстрее классического варианта, созданного еще в 60-х годах. ДПФ — один из столпов цифровой обработки сигналов: например, он применяется в алгоритмах компрессии изображений JPEG и звука MP3. Попытки дополнительно ускорить ДПФ предпринимались со времени разработки первоначального алгоритма, но пока существенных результатов добиться не удавалось.

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