Work at SourceForge, help us to make it a better place! We have an immediate need for a Support Technician in our San Francisco or Denver office.

Close

#1 compute only subset of the fourier transform (zero centered)

open
nobody
None
5
2012-02-16
2012-02-16
Laurent Bourgès
No

As I only need a subset of the fourier transform (centered on zero), I implemented an optimized realForward alternative: realForwardSubset(final int subSize, float[][]) where subSize corresponds to both input image size and output DFT size.

The main idea consist in avoiding computing frequencies higher than desired subSize and using only the input image << FFT size to use less memory (subSize x DFT size instead of size x size) and skip FFT over zero values i.e. avoid zero padding.

I provide the pacthed FloatFFT_2D class to have your review / point of view. The only problem I guess concerns data in the first column (re/im) that contains values for zero, rows/2 and columns/2 (mixed).

I also added another optimization to avoid allocating too large arrays newRows / newCols for very large FFT (>64K) and work in parallel on chunks in a sort of pipeline (rows => output) > (output => columns) > final subpart. Doing so, it only consumes 512M to compute an FFT 256K for an output size of 8192.

I think such enhancement could be generalized to other FFT methods and at least integrated to the next JTransforms release. What is your opinion ?

Here are benchmark results limited to 16K full FFT due to the memory limit on my computer (2g):
Full FFT:
11:42:42.588 INFO [main] fits.ImageFitsTest - FFT realForward[2048 - 2048]: average duration = 153.7692635 ms (10 iterations).
11:42:50.915 INFO [main] fits.ImageFitsTest - FFT realForward[4096 - 4096]: average duration = 433.6015159 ms (10 iterations).
11:43:13.437 INFO [main] fits.ImageFitsTest - FFT realForward[8192 - 8192]: average duration = 1777.2291536 ms (10 iterations).
11:44:51.746 INFO [main] fits.ImageFitsTest - FFT realForward[16384 - 16384]: average duration = 8456.270368399999 ms (10 iterations).
FFT Subset:
11:42:44.607 INFO [main] fits.ImageFitsTest - FFT realForward[512 - 2048]: average duration = 30.388753700000002 ms (10 iterations). (5 times faster)
11:42:53.209 INFO [main] fits.ImageFitsTest - FFT realForward[512 - 4096]: average duration = 64.2379522 ms (10 iterations). (6.9 times faster)
11:43:16.189 INFO [main] fits.ImageFitsTest - FFT realForward[512 - 8192]: average duration = 111.0820636 ms (10 iterations). (16 times faster)
11:44:56.155 INFO [main] fits.ImageFitsTest - FFT realForward[512 - 16384]: average duration = 261.37946509999995 ms (10 iterations). (32.3 times faster)

Discussion

1 2 3 > >> (Page 1 of 3)
  • provided patch having realForwardSubset(subSize, float[][])

     
    Attachments
  • You actually make it seem so easy with your presentation but I find this topic to be actually something that I think I would never understand. It seems too complex and very broad for me. I am looking forward for your next post, I?ll try to get the hang of it!
    http://guccibagssales.tumblr.com

     
  • I think other site proprietors should take this website as an model, very clean and magnificent user friendly style and design, let alone the content. You are an expert in this topic!
    http://seosoftwaresales.tumblr.com

     
  • It??s really a cool and useful piece of information. I am satisfied that you just shared this useful info with us. Please keep us informed like this. Thanks for sharing.
    wow gold usa http://wowgoldus.tumblr.com/

     
  • Hey, you used to write fantastic, but the last several posts have been kinda boringK I miss your great writings. Past several posts are just a little bit out of track! come on!
    wow gold prices http://iwowgold.tumblr.com/

     
  • Hi, I log on to your blogs like every week. Your humoristic style is witty, keep up the good work!
    cheap wow gold http://cheapgold4wow.tumblr.com/

     
  • You actually make it seem so easy with your presentation but I find this matter to be actually something that I think I would never understand. It seems too complex and extremely broad for me. I'm looking forward for your next post, I will try to get the hang of it!
    diablo 3 gold http://www.d3eye.com

     
  • My brother recommended I might like this blog. He was totally right. This post actually made my day. You cann't imagine simply how much time I had spent for this info! Thanks!
    chanel outlet http://chaneloutletonline.weebly.com/

     
  • Ive been exploring for a bit for any high quality articles or blog posts on this kind of space . Exploring in Yahoo I eventually stumbled upon this web site. Studying this info So i am satisfied to express that I have a very just right uncanny feeling I discovered just what I needed. I so much unquestionably will make sure to dont disregard this web site and provides it a glance on a constant basis|regularly}.
    chanel classic flap bag http://chanelclassicflapbag.ezweb123.com/

     
  • I am always invstigating online for ideas that can facilitate me. Thx!
    chanel bag http://chanelbag.onsugar.com/

     
1 2 3 > >> (Page 1 of 3)