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-le...@python.org > https://mail.python.org/mailman3/lists/numpy-discussion.python.org/ > Member address: ralf.gomm...@googlemail.com >
_______________________________________________ NumPy-Discussion mailing list -- numpy-discussion@python.org To unsubscribe send an email to numpy-discussion-le...@python.org https://mail.python.org/mailman3/lists/numpy-discussion.python.org/ Member address: arch...@mail-archive.com
