MATLAB Central Newsreader - FFT and small prime factors

FFT and small prime factors

Rodrigo — Sun, 08 Nov 2009 03:46:02 -0500

I'm writing some code that will be used to convolve large amounts of data in a little time as possible (~1 million 1D ffts, each of of which has a few thousand entries). To make this run as fast as possible I was wondering if anyone knew of an algorithm that approximates a number N with the closest number M such that M=2^a*3^b*5^c (a,b,c integers)

Doing this for a single prime factor is trivial, but the resolution in M is such that you end up padding with too many zeros or throwing away a lot of data. Adding the extra factors improves the resolution and should not reduce the performance of the algorithm too much.

I can think of a direct search algorithm for this using the distance of a point to a hyperplane as a metric, but I was hoping there was a more elegant solution to this.

Cheers

Re: FFT and small prime factors

Rodrigo — Sun, 08 Nov 2009 23:18:01 -0500

"Rodrigo" <guerra.remove.this@physics.harvard.edu> wrote in message <hd5etq$j9f$1@fred.mathworks.com>...
> I'm writing some code that will be used to convolve large amounts of data in a little time as possible (~1 million 1D ffts, each of of which has a few thousand entries). To make this run as fast as possible I was wondering if anyone knew of an algorithm that approximates a number N with the closest number M such that M=2^a*3^b*5^c (a,b,c integers)
>
> Doing this for a single prime factor is trivial, but the resolution in M is such that you end up padding with too many zeros or throwing away a lot of data. Adding the extra factors improves the resolution and should not reduce the performance of the algorithm too much.
>
> I can think of a direct search algorithm for this using the distance of a point to a hyperplane as a metric, but I was hoping there was a more elegant solution to this.
>
> Cheers

Any thoughts?

Re: FFT and small prime factors

TideMan — Sun, 08 Nov 2009 23:42:07 -0500

On Nov 9, 12:18 pm, "Rodrigo" <guerra.remove.t...@physics.harvard.edu>
wrote:
> "Rodrigo" <guerra.remove.t...@physics.harvard.edu> wrote in message <hd5etq$j9...@fred.mathworks.com>...
> > I'm writing some code that will be used to convolve large amounts of data in a little time as possible (~1 million 1D ffts, each of of which has a few thousand entries). To make this run as fast as possible I was wondering if anyone knew of an algorithm that approximates a number N with the closest number M such that M=2^a*3^b*5^c (a,b,c integers)
>
> > Doing this for a single prime factor is trivial, but the resolution in M is such that you end up padding with too many zeros or throwing away a lot of data. Adding the extra factors improves the resolution and should not reduce the performance of the algorithm too much.
>
> > I can think of a direct search algorithm for this using the distance of a point to a hyperplane as a metric, but I was hoping there was a more elegant solution to this.
>
> > Cheers
>
> Any thoughts?

I looked at it and couldn't figure out what you were getting at.
Do you want an algorithm that calculates numbers that have primes of
2, 3, 5 (a la Singleton's FFT that takes numbers with primes up to
23), or what?
And if each FFT is for only a few thousand points, I don't know what
you're worried about.
Just use Matlab's FFT on whatever number you have. It is very fast.

Re: FFT and small prime factors

dbd — Mon, 09 Nov 2009 00:28:46 -0500

On Nov 7, 7:46 pm, "Rodrigo" <guerra.remove.t...@physics.harvard.edu>
wrote:
> I'm writing some code that will be used to convolve large amounts of data in a little time as possible (~1 million 1D ffts, each of of which has a few thousand entries). To make this run as fast as possible I was wondering if anyone knew of an algorithm that approximates a number N with the closest number M such that M=2^a*3^b*5^c (a,b,c integers)
>
> Doing this for a single prime factor is trivial, but the resolution in M is such that you end up padding with too many zeros or throwing away a lot of data. Adding the extra factors improves the resolution and should not reduce the performance of the algorithm too much.
>
> I can think of a direct search algorithm for this using the distance of a point to a hyperplane as a metric, but I was hoping there was a more elegant solution to this.
>
> Cheers

Rodrigo

I'm not going to suggest an algorithm for you, but I will suggest
reasons why I don't think the algorithm you seek will provide the most
efficient solution to your fft application.
1) solutions should be weighted by the 'efficiency' of the kernels
used
2) the most efficient kernels may well not be primes.
3) the values of the weights depend on the particulars of the hardware
and software implementations considered.

I would suggest that you look at the 'automatic generation of fft
codes' literature to find examples of solutions that might match your
intended implementation. There has been considerable effort towards
optimization specific to implementation characteristics.

A couple of examples for different architectures that include
discussion of the problem and some if the approaches that have been
tried are:

http://vgrads.rice.edu/publications/pdfs/AEOS_Codegenerator_For_FFT.pdf
http://www.iseclab.org/people/pw/papers/vecpar04

Google can find you many more. If you have knowledge of the intended
platform, language, software environment, etc., consider adding that
to your search terms.

Dale B. Dalrymple

Re: FFT and small prime factors

Timothy — Wed, 14 Apr 2010 09:52:03 -0400

This will do it for integers lower than your input (just supply the largest prime factor). It is easy to make it find the next highest integer, also (just put a while loop and increase j on each iteration).

function out = nearestLowPrimeFac(in,low)

for i=1:in-1

    j = in - i;

    if max(factor(j)) == low, break, end

end

out = j;

end

"Rodrigo" <guerra.remove.this@physics.harvard.edu> wrote in message <hd5etq$j9f$1@fred.mathworks.com>...
> I'm writing some code that will be used to convolve large amounts of data in a little time as possible (~1 million 1D ffts, each of of which has a few thousand entries). To make this run as fast as possible I was wondering if anyone knew of an algorithm that approximates a number N with the closest number M such that M=2^a*3^b*5^c (a,b,c integers)
>
> Doing this for a single prime factor is trivial, but the resolution in M is such that you end up padding with too many zeros or throwing away a lot of data. Adding the extra factors improves the resolution and should not reduce the performance of the algorithm too much.
>
> I can think of a direct search algorithm for this using the distance of a point to a hyperplane as a metric, but I was hoping there was a more elegant solution to this.
>
> Cheers

Re: FFT and small prime factors

John D'Errico — Wed, 14 Apr 2010 12:34:05 -0400