On the Usage of the Sparse Fourier Transform in Ultrasound Propagation Simulation
Authors: 
Ondrej Olsak, Jiri JarosAuthors Info & Claims
Ondrej Olsak, Jiri JarosAuthors Info & ClaimsPages 107 - 113
Abstract
The Fourier transform is an algorithm for transforming the signal from the space/time domain into the frequency domain. This algorithm is essential for applications like image processing, communication, medicine, differential equations solvers, and many others. In some of these applications, most of the Fourier coefficients are small or equal to zero. This property of the signals is used by the Sparse Fourier transform which estimates significant coefficients of the signal with a lower time complexity than the Fourier transform. The goal of this paper is to evaluate available implementations of the Sparse Fourier transform on a set of benchmarks solving the ultrasound wave propagation in 1D, 2D, and 3D heterogeneous media. The results show that the fastest available implementation in 1D domains is MSFFT, however, it is not possible to use it in our implementation of the 2D Sparse Fourier transform. Thus the AAFFT 0.9 is selected for our implementation of the 2D Sparse Fourier transform as the most stable and acceptably fast implementation. The results on 3D simulation data show, that by using the SpFFT library it is possible to reduce the computation time of the Fourier transform in ultrasound wave propagation simulation.
References
[1]
2014. FFTW home page. https://www.fftw.org/
[2]
2019. SpFFT Documentation. https://spfft.readthedocs.io/en/latest/
[3]
2023. IT4I technical information of the Barbora supercomputer page. https://www.it4i.cz/en/infrastructure/barbora
[4]
2023. IT4I technical information of the Karolina supercomputer page. https://www.it4i.cz/en/infrastructure/karolina
[5]
I. Ben Segal and M. A. Iwen. 2010. Signal Approximation via the Gopher Fast Fourier Transform. AIP Conference Proceedings 1301, 1 (2010), 494–502. https://doi.org/10.1063/1.3526650 arXiv:https://aip.scitation.org/doi/pdf/10.1063/1.3526650
[6]
Andrew Christlieb, David Lawlor, and Yang Wang. 2013. A Multiscale Sub-linear Time Fourier Algorithm for Noisy Data. https://doi.org/10.48550/ARXIV.1304.4517
[7]
James W. Cooley and John W. Tukey. 1965. An Algorithm for the Machine Calculation of Complex Fourier Series. Math. Comp. 19, 90 (1965), 297–301. http://www.jstor.org/stable/2003354
[8]
Anna Gilbert, Sudipto Guha, Piotr Indyk, Senthilmurugan Muthukrishnan, and Martin Strauss. 2002. Near-optimal sparse Fourier representations via sampling. Conference Proceedings of the Annual ACM Symposium on Theory of Computing, 152–161. https://doi.org/10.1145/509907.509933
[9]
Anna Gilbert, Senthilmurugan Muthukrishnan, and Martin Strauss. 2004. Improved Time Bounds for Near-Optimal Sparse Fourier Representations. Proceedings of SPIE - The International Society for Optical Engineering 5914 (01 2004). https://doi.org/10.1117/12.615931
[10]
S. Gottlieb and D. Gottlieb. 2009. Spectral methods. Scholarpedia 4, 9 (2009), 7504. https://doi.org/10.4249/scholarpedia.7504 revision #91796.
[11]
Haitham Hassanieh, Fadel Adib, Dina Katabi, and Piotr Indyk. 2012. Faster GPS via the Sparse Fourier Transform. In Proceedings of the 18th Annual International Conference on Mobile Computing and Networking (Istanbul, Turkey) (Mobicom ’12). Association for Computing Machinery, New York, NY, USA, 353–364. https://doi.org/10.1145/2348543.2348587
[12]
Haitham Hassanieh, Piotr Indyk, Dina Katabi, and Eric Price. 2012. Simple and Practical Algorithm for Sparse Fourier Transform. In Proceedings of the 2012 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 1183–1194. https://doi.org/10.1137/1.9781611973099.93 arXiv:https://epubs.siam.org/doi/pdf/10.1137/1.9781611973099.93
[13]
A. Hosokawa. 2005. Simulation of ultrasound propagation through bovine cancellous bone using elastic and Biot’s finite-difference time-domain methods. The Journal of the Acoustical Society of America 118, 3 (2005), 1782–1789. https://doi.org/10.1121/1.2000767 arXiv:https://doi.org/10.1121/1.2000767
[14]
A. Hosokawa. 2005. Simulation of ultrasound propagation through bovine cancellous bone using elastic and Biot’s finite-difference time-domain methods. The Journal of the Acoustical Society of America 118, 3 (09 2005), 1782–1789. https://doi.org/10.1121/1.2000767 arXiv:https://pubs.aip.org/asa/jasa/article-pdf/118/3/1782/15275850/1782_1_online.pdf
[15]
Mark Iwen, Anna Gilbert, and And Strauss. 2007. Empirical evaluation of a sub-linear time sparse DFT algorithm. Communications in Mathematical Sciences 5 (01 2007), 981–998. https://doi.org/10.4310/CMS.2007.v5.n4.a13
[16]
M. A. Iwen. 2010. Improved Approximation Guarantees for Sublinear-Time Fourier Algorithms. https://doi.org/10.48550/ARXIV.1010.0014
[17]
Jiri Jaros, Bradley Treeby, and Alistair Rendell. 2012. Use of multiple GPUs on shared memory multiprocessors for ultrasound propagation simulations. Conferences in Research and Practice in Information Technology Series 127, 43–52.
[18]
Zhikang Jiang, Jie Chen, and Bin Li. 2021. Empirical Evaluation of Typical Sparse Fast Fourier Transform Algorithms. IEEE Access 9 (2021), 97100–97119. https://doi.org/10.1109/ACCESS.2021.3095071
[19]
Zhikang Jiang, Jie Chen, and Bin Li. 2021. Empirical Evaluation of Typical Sparse Fast Fourier Transform Algorithms. IEEE Access 9 (2021), 97100–97119. https://doi.org/10.1109/ACCESS.2021.3095071
[20]
Michael Lustig, David L. Donoho, Juan M. Santos, and John M. Pauly. 2008. Compressed Sensing MRI. IEEE Signal Processing Magazine 25, 2 (2008), 72–82. https://doi.org/10.1109/MSP.2007.914728
[21]
Jackson W. Massey and Ali E. Yilmaz. 2016. AustinMan and AustinWoman: High-fidelity, anatomical voxel models developed from the VHP color images. In 2016 38th Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC). 3346–3349. https://doi.org/10.1109/EMBC.2016.7591444
[22]
Sami Merhi, Ruochuan Zhang, Mark A. Iwen, and Andrew Christlieb. 2017. A New Class of Fully Discrete Sparse Fourier Transforms: Faster Stable Implementations with Guarantees. https://doi.org/10.48550/ARXIV.1706.02740
[23]
D.H. Mugler and R.A. Scott. 1988. Fast fourier transform method for partial differential equations, case study: The 2-D diffusion equation. Computers & Mathematics with Applications 16, 3 (1988), 221–228. https://doi.org/10.1016/0898-1221(88)90182-4
[24]
Elias Rajaby and Sayed Sayedi. 2022. A structured review of sparse fast Fourier transform algorithms. Digital Signal Processing 123 (01 2022), 103403. https://doi.org/10.1016/j.dsp.2022.103403
[25]
Chaojun Shou, Xiaoyu Chen, Hao-Li Liu, and Po-Hsiang Tsui. 2016. Using Short-Time Fourier Transform to Ultrasound Signals for Fatty Liver Detection. International Journal of Signal Processing Systems (08 2016), 300–303. https://doi.org/10.18178/ijsps.4.4.300-303
[26]
Sunaina, Mansi Butola, and Kedar Khare. 2018. Calculating numerical derivatives using Fourier transform: some pitfalls and how to avoid them. European Journal of Physics 39, 6 (10 2018), 065806. https://doi.org/10.1088/1361-6404/aadda6
[27]
Bradley Treeby, Ben Cox, and Jiri Jaros. 2016. k-Wave A MATLAB toolbox for the time domain simulation of acoustic wave fields User Manual. (2016). http://www.k-wave.org/manual/k-wave_user_manual_1.1.pdf
[28]
E. Bradley Treeby, Jiri Jaros, P. Alistair Rendell, and T. Ben Cox. 2012. Modeling nonlinear ultrasound propagation in heterogeneous media with power law absorption using a k-space pseudospectral method. Journal of the Acoustical Society of America 131, 6 (2012), 4324–4336. https://doi.org/10.1121/1.4712021
[29]
Praveen K. Yenduri, Aaron Z. Rocca, Aswin S. Rao, Shahrzad Naraghi, Michael P. Flynn, and Anna C. Gilbert. 2012. A Low-Power Compressive Sampling Time-Based Analog-to-Digital Converter. IEEE Journal on Emerging and Selected Topics in Circuits and Systems 2, 3 (2012), 502–515. https://doi.org/10.1109/JETCAS.2012.2221832
Index Terms
- On the Usage of the Sparse Fourier Transform in Ultrasound Propagation Simulation
Recommendations
Techniques for Efficient Fourier Transform Computation in Ultrasound Simulations
HPDC '24: Proceedings of the 33rd International Symposium on High-Performance Parallel and Distributed ComputingNoninvasive ultrasound surgeries represent a rapidly growing field in medical applications. Preoperative planning often relies on computationally expensive ultrasound simulations. This paper explores methods to accelerate these simulations by reducing ...
Two‐dimensional sparse fractional Fourier transform and its applications
Highlights- Efficient estimation of sampled 2D DFRFT utilizing the sparse nature of the signal.
AbstractThe discrete fractional Fourier transform is an excellent tool in non-stationary signal processing. And an efficient and accurate computation is important for the two-dimensional discrete fractional Fourier transform (2D DFRFT). ...
Representation of the Fourier Transform by Fourier Series
The analysis of the mathematical structure of the integral Fourier transform shows that the transform can be split and represented by certain sets of frequencies as coefficients of Fourier series of periodic functions in the interval $$[0,2\pi)$$ . In this paper we ...
Comments
Information & Contributors
Information
Published In
September 2023
226 pages
ISBN:9798400708152
DOI:10.1145/3632047
Copyright © 2023 Owner/Author.
This work is licensed under a Creative Commons Attribution International 4.0 License.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 27 February 2024
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Funding Sources
- Ministry of Education, Youth and Sports of the Czech Republic through the e-INFRA CZ
- European Unions Horizon Europe research and innovation programme
- Brno University of Technology
Conference
ICBRA 2023
ICBRA 2023: 2023 the 10th International Conference on Bioinformatics Research and Application
September 22 - 24, 2023
Barcelona, Spain
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 100Total Downloads
- Downloads (Last 12 months)100
- Downloads (Last 6 weeks)17
Reflects downloads up to 23 Oct 2024
Other Metrics
Citations
View Options
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML FormatGet Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in