Candes E., Demanet L., Ying L. A Fast Butterfly Algorithm for the Computation of Fourier Integral Operators

Статья. — Multiscale Model. Simul., 7(4), pp.1727–1750. — 24 pages. — [DOI. 10.1137/080734339].Тема статьи — быстрое вычисление интегральных операторов Фурье на неравномерной сетке (при наличии джиттера, например). В двумерном случае вычисление такого интеграла имеет неприемлемую сложность O(N⁴). Предлагаемый алгоритм построен по известной схеме "бабочка" и в случае двух измерений имеет близкую к оптимальной сложность O(N²logN).