Services & Resources / Wolfram Forums
-----
 /
MathGroup Archive
2004
*January
*February
*March
*April
*May
*June
*July
*August
*September
*October
*November
*December
*Archive Index
*Ask about this page
*Print this page
*Give us feedback
*Sign up for the Wolfram Insider

MathGroup Archive 2004

[Date Index] [Thread Index] [Author Index]

Search the Archive

Re: convolution vs. NMinimize

  • To: mathgroup at smc.vnet.net
  • Subject: [mg52445] Re: convolution vs. NMinimize
  • From: Bill Rowe <readnewsciv at earthlink.net>
  • Date: Sat, 27 Nov 2004 01:40:56 -0500 (EST)
  • Sender: owner-wri-mathgroup at wolfram.com

On 11/26/04 at 1:04 AM, lupos at cheerful.com (robert) wrote:

>especialy (but not only) with samplelegths which are powers of 2
>convolution can be done efficiently by FFT (Mathematica Fourier[])
>the "convolution theorem" states that to perform convolution(f,g)
>you may take the the fourier transforms F=Fourier[f] and
>G=Fourier[g] and get the convolution by calculating
>InverseFourier[F*G]

>for a sample length n

>Fourier[] calculates in n*Log[n] time (because of FFT)
>ListConvolve[] calculates in n*n time

>the differnece is enormous for large n.

I am pretty sure ListConvolve makes use of the fast fourier transform. In fact, a quick check

data=Table[Random[],{65536}];
Timing[ListConvolve[{1,-1},data];]
{0.04 Second,Null}

data=Table[Random[],{2^20}];
Timing[ListConvolve[{1,-1},data];]
{0.8 Second,Null}

2^20 Log[2^20]/(2^16 Log[2^16])//N
20.

indicates the time for ListConvolve is proportional to n Log[n]
--
To reply via email subtract one hundred and four


  • Prev by Date: Re: Automatic numbered equations
  • Next by Date: Re: Non-algebraic solution
  • Previous by thread: Re: convolution vs. NMinimize
  • Next by thread: launching a kernel on a remote linux machine through ssh from a linux machine