Эффективная реализация алгоритма быстрого преобразования Фурье на нерегулярных сетках
Автор: Матвеев Алексей Сергеевич, Никитин Виктор Валерьевич, Романенко Алексей Анатольевич, Дучков Антон Альбертович
Журнал: Проблемы информатики @problem-info
Рубрика: Параллельное системное программирование и вычислительные технологии
Статья в выпуске: 3 (32), 2016 года.
Бесплатный доступ
Статья посвящена преобразованию Фурье на нерегулярных сетках (USFFT), популярному средству анализа во многих естественнонаучных задачах. Большинство практических задач, использующих USFFT, имеют большой объем данных, что приводит к значительным вычислительным затратам. В данной работе предложена реализация алгоритма USFFT, использующая такие особенности современных центральных процессоров как параллелизм и наличие большого кэша данных. Оптимизация последовательной программы позволила сократить время выполнения наиболее трудоемкого этапа преобразования в два раза, а последующее распараллеливание дало тринадцатикратное ускорение на вычислительном узле с 16 ядрами.
Быстрое преобразование фурье, нерегулярные сетки, оптимизация, параллелизм
Короткий адрес: https://sciup.org/14320315
IDR: 14320315
Список литературы Эффективная реализация алгоритма быстрого преобразования Фурье на нерегулярных сетках
- Coolev J. W., Tukev J. W. An algorithm for the machine calculation of complex Fourier series//Mathematics of computation. 1965. T. 19. N 90. P. 297-301.
- Intel Math Kernel Library (Intel MKL) //https://software.intel.com/en-us/intel-mkl
- cuFFT | NVIDIA Developer //https://developer.nvidia.com/cufft
- FFTW Home page //http://www.fftw.org
- Bracewell R. N. Strip integration in radio astronomy//Australian Journal of Physics. 1956. T. 9. N 2. P. 198-217.
- Duchkov A. A., Andersson F., De Hoop M. V. Discrete almost-symmetric wave packets and multiscale geometrical representation of () waves//Geoscience and Remote Sensing, IEEE Transactions on. 2010. T. 48. N 9. P. 3408-3423.
- Bevlkin G., Burridge R. Linearized inverse scattering problems in acoustics and elasticity//Wave motion. 1990. T. 12. N 1. P. 15-52.
- Zwartjes P. M. Sacchi M. D. Fourier reconstruction of nonuniformlv sampled, aliased seismic data//Geophysics. 2006. T. 72. N 1. P. V21-V32.
- Dutt A., Rokhlin V. Fast Fourier transforms for nonequispaced data//SIAM Journal on Scientific computing. 1993. T. 14. N 6. P. 1368-1393.
- Bevlkin G. On the fast Fourier transform of functions with singularities//Applied and Computational Harmonic Analysis. 1995. T. 2. N 4. P. 363-381.
- Greengard L., Lee J. Y. Accelerating the nonuniform fast Fourier transform//SIAM review. 2004. T. 46. N 3. P. 443-454.
- Fessler J. A., Sutton B. P. Nonuniform fast Fourier transforms using min-max interpolation//Signal Processing, IEEE Transactions on. 2003. T. 51. N 2. P. 560-574.
- NUFFT page //http://www.cims.nyu.edu/cmcl/Clll/nufft.html
- NFFT -TU Chemnitz //https://www-user.tu-chemnitz.de/$\sim$potts/nfft/
- Andersson F. Algorithms for unequally spaced fast Laplace transforms//Applied and Computational Harmonic Analysis. 2013. T. 35. N 3. P. 419-432.
- Herman G. Т., Louis A. K., Natterer F. (ed.). Mathematical methods in tomography: proceedings of a conference held in Oberwolfach, Germany, 5-11 June, 1990. Springer, 2006.
- Yilmaz O. Seismic data analysis. Tulsa: Society of exploration geophvsicists, 2001. Т. 1. P. 74170-2740.
- Tretiak O., Metz C. The exponential Radon transform//SIAM Journal on Applied Mathematics. 1980. T. 39. N 2. P. 341-354.
- Natterer F. Inversion of the attenuated Radon transform//Inverse problems. 2001. T. 17. N 1. P. 113.
- Shepp L. A., Logan B. F. The Fourier reconstruction of a head section//Nuclear Science, IEEE Transactions on. 1974. T. 21. N 3. P. 21-43.
- Barrett H. H., Wilson D. W., Tsui В. M. W. Noise properties of the EM algorithm. I. Theory//Physics in medicine and biology. 1994. T. 39. N 5. P. 833.
- Yan M. Vese L. A. Expectation maximization and total variation-based model for computed tomography reconstruction from undersampled data//SPIE Medical Imaging. International Society for Optics and Photonics, 2011. P. 79612X-79612X-8.
- Champlev K. SPECT reconstruction using the expectation maximization algorithm and an exact inversion formula: дис. MS Thesis, Oregon State University, 2004.
- Dempster А. P., Laird N. M., Rubin D. В. Maximum likelihood from incomplete data via the EM algorithm//Journal of the royal statistical society. Series В (methodological). 1977. P. 1-38.
- Miqueles E. X., Helou E. S., De Pierro A. R. Generalized Backprojection Operator: Fast Calculation//Journal of Physics: Conference Series. IOP Publishing, 2014. T. 490. N 1. P. 012148.
