Implementación software eficiente de la Transformada de Fourier Escasa casi óptima para el caso con ruido
Main Article Content
Keywords
Transformada de Fourier Escasa, programación multinúcleo, agrupamiento de computadoras
Resumen
En este artículo se presenta una implementación software optimizada (sFFT- 4.0) del algoritmo Transformada Rápida de Fourier Escasa (sFFT) Casi Óptimo para el caso con ruido. En primer lugar, se desarrolló una versión modificada del algoritmo sFFT Casi Óptimo para el caso con ruido, esta modificación resuelve los problemas de exactitud de la versión origial al modificar la ventana plana y los procedimientos; y en segundo lugar, se implementó el algoritmo modificado en una plataforma multinúcleo compuesta de ocho núcleos. Los resultados experimentales en el agrupamiento de computadores muestran que la implementación desarrollada es más rápida que el cálculo directo usando la biblioteca FFTW bajo ciertas condiciones de escasés y tamaño de señal, y mejora los tiempos de ejecución de implementaciones previas como sFFT-2.0. Al mejor conocimiento de los autores, la implementación desarrollada es la primera del algoritmo sFFT Casi Óptimo para el caso con ruido.
MSC: 65T50
Descargas
Referencias
[2] ——, “Nearly optimal sparse Fourier transform,” in Proceedings of the 44th symposium on Theory of Computing (STOC), New York, USA, May 2012. pp. 563–578.
[3] P. Indyk, M. Kapralov, and and Eric Price, “(Nearly) Sample-Optimal Sparse Fourier Transform,” in ACM-SIAM Symposium on Discrete Algorithms (SODA), Portland, USA, 2014.
[4] H. Hassanieh, L. Shi, O. Abari, E. Hamed, and D. Katabi, “GHz-wide sensing and decoding using the sparse Fourier transform,” in INFOCOM, 2014 Proceedings IEEE. IEEE, 2014, pp. 2256–2264. [Online]. Available: http://dx.doi.org/10.1109/INFOCOM.2014.6848169
[5] A. C. Gilbert, S. Muthukrishnan, and M. J. Strauss, “Improved time bounds for near-optimal sparse Fourier representations,” in Proceedings of SPIE Wavelets XI, San Diego, USA, 2005, pp. 1–15.
[6] A. C. Gilbert, Y. Li, E. Porat, and M. J. Strauss, “Approximate sparse recovery: optimizing time and measurements,” in Proceedings of the 42nd ACM symposium on Theory of computing, Cambridge, USA, 2012.
[7] A. C. Gilbert, M. J. Strauss, and J. A. Tropp, “A Tutorial on Fast Fourier Sampling,” IEEE Signal Processing Magazine, vol. 25, no. 2, pp. 57–66, 2008. [Online]. Available: http://dx.doi.org/10.1109/MSP.2007.915000
[8] M. Frigo and S. G. Johnson, FFTW, 3rd ed., Massachusetts Institute of Technology, 2012. [Online]. Available: http://www.fftw.org/
[9] C. Wang, M. Araya-Polo, S. Chandrasekaran, A. St-Cyr, B. Chapman, and D. Hohl, “Parallel Sparse FFT,” in Proceedings of the 3rd Workshop on Irregular Applications: Architectures and Algorithms,
New York, NY, USA, 2013, pp. 10:1—-10:8. [Online]. Available: http://dx.doi.org/10.1145/2535753.2535764
[10] J. Hu, Z. Wang, Q. Qiu, W. Xiao, and D. J. Lilja, “Sparse Fast Fourier Transform on GPUs and Multi-core CPUs,” in Computer Architecture and High Performance Computing (SBAC-PAD), 2012 IEEE
24th International Symposium on, Oct. 2012, pp. 83–91. [Online]. Available: http://dx.doi.org/10.1109/SBAC-PAD.2012.34
[11] J. Schumacher, “High Performance Sparse Fast Fourier Transform,” Master Thesis, ETH Zurich, Department of Computer Science, 2013. [Online]. Available: http://goo.gl/3alHvS
[12] A. Dutt and V. Rokhlin, “Fast Fourier transforms for nonequispaced data, II,” Applied and Computational Harmonic Analysis, vol. 2, no. 1, pp. 85–100, 1995. [Online]. Available: http://dx.doi.org/10.1006/acha.1995.1007
[13] M. Abramowitz and I. A. Stegun, Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 10th ed. Washington, DC, USA: Dover, 1972.
[14] OpenMP, OpenMP Application Program Interface, OpenMP Architecture Review Board Std., 2013.