On Wed, Feb 28, 2024 at 6:59 AM camrymanjr--- via NumPy-Discussion < numpy-discussion@python.org> wrote:
Good day!
My name is Alexander Levin.
My colleague and I did a project on optimisation of two-dimensional Fourier transform algorithm six months ago. We took your implementation of numpy fft2d as a unit of quality.
Thanks for sharing Alexander.
In the course of our research we found out that initially mathematically the method uses a far from optimal algorithm. As you may know, your operation goes first by rows then by columns applying a one-dimensional transformation. After spending some time researching mathematical papers on this topic, we found and implemented a new approach, the so-called Cooley-Tukey butterfly, optimised by Russian mathematicians in 2016.
The output is a completely new approach, where we immediately apply a two-dimensional operation and save a serious proportion of time on it. As a result, we wrote a C++ package for Python, using Cython as a wrapper. The result was the package and an article on Medium describing the process. On tests for matrices ranging in size from 2048x512 to 8192x8192, our algorithm outperformed the NumPy transformation by an average of 50% in time.
Did you also benchmark against `scipy.fft` by any chance? SciPy uses a newer C++ version of PocketFFT. In NumPy we just switched over from the older C code of PocketFFT to the newer C++ code: https://github.com/numpy/numpy/pull/25536. That PR also solves the upcasting that your Medium article touches on; we now have proper float32/complex64 support. Note that SciPy also has a multi-threaded version, which you can enable with the `workers` keyword. It'd also be interesting perhaps to benchmark memory usage, since your article touches on eliminating temporary arrays. After discussing this matter with my colleague with whom we did the above
development, we came to a common desire to share our results with you. Your company has been making a huge contribution to the IT community for almost 20 years on a pro bono basis. We share your philosophy and so we want to make the CS world a better place by providing you with our code to optimise the approach in an existing operation in your package.
Great to hear that. Note that we're not a company - more a loosely organized team of mostly volunteers and some folks who get to work on NumPy as part of their day job at a company or university.
We would like to offer you our development version, though it'll need some minor improvements, we'd love to finish them collaboratively with you and hear your thoughts regarding what we have discovered and done so far. We'd be honored to help you and become NumPy contributors.
Performance improvements are always of interest, so if this is an algorithmic improvement without loss of accuracy, then that sounds very relevant. And more contributors are always welcome! Cheers, Ralf I trust that our vision will resonate with you and that you will agree with
us. I invite you to read our quick article about the process, which I have linked below, and our fully functioning package and share your views on our contribution to NumPy. We are willing to edit the code to fit your standards, as we believe that the best use of our work will be to contribute to the development of technology in the world.
Thank you for your time. We look forward to your response and opinion.
Medium Article about the process: https://medium.com/p/7963c3b2f3c9 GitHub Source code Repository: https://github.com/2D-FFT-Project/2d-fft _______________________________________________ NumPy-Discussion mailing list -- numpy-discussion@python.org To unsubscribe send an email to numpy-discussion-leave@python.org https://mail.python.org/mailman3/lists/numpy-discussion.python.org/ Member address: ralf.gommers@googlemail.com