Преобразование Фурье в 3 измерениях на неоднородной сетке в Matlab

Мне нужно рассчитать трехмерное преобразование Фурье структур, у меня есть их [x,y,z] координаты. Я думал о интерполяции в единую сетку наименьшего расстояния между точками и использовать fft, но это оказалось непрактичным в памяти, поэтому fft не может быть использован. Пример из моих [x,y,z] данных:

xyz=[ 23.1860   44.9710    5.9280
      25.5370   44.0090    4.9960
      24.5030   44.5890    6.2280
      20.0150   46.4080    7.9110
      24.9910   44.6760    7.5330
       4.8660   44.7120    8.6830
      36.7170   33.7440    6.5570
      11.1510   40.0590    5.8120
      29.2550   34.8750   10.0850
       5.4230   48.8200   12.7380
      38.2020   35.7590    1.3260 ];

Буду признателен за ваш совет

Источник

2 ответа

Решение

Я сам этим не пользовался, но рассмотрите возможность использования NFFT, размещенного на сайте Математического факультета Хемницкого технологического университета. Это уменьшает требование O(N^2) до просто O(NlogN), как в случае FFT. Кроме того, теперь он включает в себя классы Matlab для взаимодействия с mex-файлами.

Вы можете скачать несколько примеров на сайте, где показано, как взаимодействовать с MATLAB, и в faq есть инструкции по использованию в Windows+MATLAB (если вы это делаете).

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

Он лицензирован по лицензии GPL.

Источник

К сожалению, алгоритмы, которые делают БПФ настолько эффективным, просто не применимы к неоднородному случаю. Принимая во внимание, что БПФ - O(N log N), неоднородный случай - обычно O(N^2) (насколько я знаю). Все известные мне методы NUFFT основаны на интерполяции, так что вы вряд ли найдете принципиально иной способ сделать это.

Какова ваша геометрия сетки (я не могу смотреть на массивы, которые вы указали для шаблонов расстояний)? Если одно или два измерения одинаковы, вы можете применить 1 или 2D БПФ к ним независимо, а затем интерполировать только для третьего измерения. Многие проблемы в сферических координатах эффективно делают это: они используют БПФ вдоль линий постоянной широты, потому что широты обычно расположены неравномерно, чтобы использовать гауссову квадратуру, в то время как долготы являются однородными.

Greengard, L. & Lee, JY (2004). Ускорение неравномерного быстрого преобразования Фурье. Обзор SIAM, 46 (3), 443-454.

Источник
Другие вопросы по тегам