Path: news.mathworks.com!newsfeed-00.mathworks.com!solaris.cc.vt.edu!news.vt.edu!news.glorb.com!postnews.google.com!a37g2000prf.googlegroups.com!not-for-mail
From: dbd <dbd@ieee.org>
Newsgroups: comp.soft-sys.matlab
Subject: Re: FFT and small prime factors
Date: Sun, 8 Nov 2009 16:28:46 -0800 (PST)
Organization: http://groups.google.com
Lines: 47
Message-ID: <e7b59826-76fc-4520-9aa7-38cf519728bc@a37g2000prf.googlegroups.com>
References: <hd5etq$j9f$1@fred.mathworks.com>
NNTP-Posting-Host: 75.15.86.181
Mime-Version: 1.0
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable
X-Trace: posting.google.com 1257726526 22535 127.0.0.1 (9 Nov 2009 00:28:46 GMT)
X-Complaints-To: groups-abuse@google.com
NNTP-Posting-Date: Mon, 9 Nov 2009 00:28:46 +0000 (UTC)
Complaints-To: groups-abuse@google.com
Injection-Info: a37g2000prf.googlegroups.com; posting-host=75.15.86.181; 
	posting-account=E_gaFgoAAACfAhF2MzvkivNAUVGQbrBP
User-Agent: G2/1.0
X-HTTP-UserAgent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US; rv:1.9.0.15) 
	Gecko/2009101601 Firefox/3.0.15 (.NET CLR 3.5.30729),gzip(gfe),gzip(gfe)
Xref: news.mathworks.com comp.soft-sys.matlab:583443


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