Geek Answers Handbook

Fourier transform in three dimensions on an inhomogeneous grid in a matrix

I need to calculate the three-dimensional Fourier transform of structures that have their coordinates [x, y, z]. I was thinking about interpolating the smallest distance between points into a single grid and using fft, but this turned out to be impractical in memory, so fft cannot be used. Sample from my data [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 ];

Thank your recommendations

+6
source share
2 answers

I have not used this myself, but consider using NFFT , published on the website of the Faculty of Mathematics of the University of Technology Chemnitz. This reduces the requirement of O (N ^ 2) only to O (NlogN), as in the case of FFT. In addition, it now includes Matlab classes for interacting with mex files.

You can download a few examples on the site that show to interact with MATLAB, and faq has instructions for using Windows + MATLAB (if any).

NFFT requires initialization of the plan and pre-computes several things to improve performance. It seems like it will take some effort to get to know each other, but it can be very useful for you.

It is licensed under the GPL.

+5
source

Unfortunately, the algorithms that make FFTs so efficient simply do not apply to the uneven case. While the FFT is O (N log N), the uneven case is usually O (N ^ 2) (as far as I know). All of the NUFFT methods that I know of mostly rely on interpolation, so you are unlikely to find a fundamentally different way to do this.

What is the geometry of your mesh (I do not see the eye arrays that you provided for the interval patterns)? If one or two dimensions are homogeneous, you can apply 1 or 2D FFTs to them independently, and then interpolate only for the third dimension. Many problems in spherical coordinates effectively do this: they use FFT along lines of constant latitude, because latitudes are usually spaced unevenly to use Gaussian quadrature, and longitudes are uniform.

Greengard, L., and Lee, JY (2004). Acceleration of the inhomogeneous fast Fourier transform. SIAM Review, 46 (3), 443-454.

+6
source

More articles:


All Articles