6

我需要计算结构的 3D 傅里叶变换，我有它们的 [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 ];

非常感谢您的建议

4

2 回答 2

6

不幸的是，使 FFT 如此高效的算法根本不适用于非均匀情况。虽然 FFT 是 O(N log N)，但非均匀情况通常是 O(N^2)（据我所知）。我所知道的所有 NUFFT 技术基本上都依赖于插值，因此您不太可能找到一种完全不同的方法。

您的网格几何形状是什么（我无法看到您为间距模式提供的阵列）？如果其中一个或两个维度是统一的，您可以对它们单独应用 1D 或 2D FFT，然后仅对第三个维度进行插值。球坐标中的许多问题有效地做到了这一点：它们沿恒定纬度线使用 FFT，因为纬度通常不均匀地间隔以使用高斯正交，而经度是均匀的。

Greengard, L. 和 Lee, JY (2004)。加速非均匀快速傅里叶变换。暹罗评论，46（3），443-454。

于 2013-02-27T20:06:26.837 回答
5

我自己没有使用过这个，但考虑使用在开姆尼茨科技大学数学系网站上发布的NFFT 。与 FFT 情况一样，它将 O(N^2) 要求降低到仅 O(NlogN)。此外，它现在包括与 mex 文件交互的 Matlab 类。

您可以在网站上下载一些示例，以显示与 MATLAB 交互，并且常见问题解答中有关于如何在 Windows+MATLAB 中使用的说明（如果您是）。

NFFT 需要初始化一个计划并预先计算一些东西来提高性能。看起来需要一些努力才能熟悉，但可能对您很有帮助。

它是根据 GPL 许可的。

于 2013-04-01T02:06:37.503 回答