`

СПЕЦИАЛЬНЫЕ
ПАРТНЕРЫ
ПРОЕКТА

Архив номеров

BEST CIO

Определение наиболее профессиональных ИТ-управленцев, лидеров и экспертов в своих отраслях

Человек года

Кто внес наибольший вклад в развитие украинского ИТ-рынка.

Продукт года

Награды «Продукт года» еженедельника «Компьютерное обозрение» за наиболее выдающиеся ИТ-товары

 

Алгоритм MIT многократно ускоряет «быстрое преобразование Фурье»

+11
голос
Алгоритм MIT многократно ускоряет «быстрое преобразование Фурье»

Быстрое преобразование Фурье (БПФ) можно по праву назвать самым важным численным алгоритмом 20-го столетия. Его изобретение в 60-х годах прошлого столетия позволило компьютерам быстро выполнять разложение сигналов на составляющий их гармонический спектр (преобразование Фурье) и привело к активному развитию технологий сжатия цифровой информации, прогрессу в аудио и видео.

Совершенно естественно, что с самого момента его появления, ученые не оставляют попыток сделать столь полезный алгоритм еще более эффективным.

В прошлом году это удалось сделать двум сотрудникам MIT, Петру Индыку (Piotr Indyk) и Дине Катаби (Dina Katabi). Разработанная ими модификация в некоторых условиях способна выполнять преобразование Фурье в сотни раз быстрее, чем БПФ.

И вот недавно, Индык, профессор информатики и компьютерной техники и член группы Теории вычислений, входящей в состав лаборатории CSAIL (Computer Science and Artificial Intelligence Laboratory), вместе с возглавляемым им коллективом, сделал следующий шаг в оптимизации алгоритма, существенно сократив количество выборок исходного сигнала, требуемых для выполнения преобразования Фурье.

В статье, подготовленной для январского симпозиума по дискретным алгоритмам ACM-SIAM, он описывает алгоритм, способный осуществлять преобразование Фурье на количестве выборок, близком к теоретическому минимальному пределу. В последней же версии алгоритма этот теоретический минимум уже достигнут.

По мнению Индыка, это достижение позволит значительно уменьшить затраты времени на сканирование пациентов в установках магнитного и ядерного магнитного резонанса, а астрономы смогут получить более детальные радиоизображения Вселенной.

Алгоритм получил название SFFT (Sparse Fast Fourier Transform). Естественные сигналы часто бывают «разреженными» (sparse), то есть определяются относительно небольшим числом ненулевых частотных компонентов. Хаотические сигналы, напротив, характеризуются соизмеримой амплитудой для всех частот. Новое быстрое преобразование SFFT заметно ускоряет вычисления только для разреженных сигналов.

Дізнайтесь більше про мікро-ЦОД EcoStruxure висотою 6U

+11
голос

Напечатать Отправить другу

Читайте также

 

Slack подает жалобу на Microsoft и требует антимонопольного расследования от ЕС

 
Реклама

  •  Home  •  Рынок  •  ИТ-директор  •  CloudComputing  •  Hard  •  Soft  •  Сети  •  Безопасность  •  Наука  •  IoT