Seems dumb*, but what the hey: (data sets are 1D PCM audio data) Convolution is O(n*m) where n is the length of one vector to be convolved, m is the length of the other vector. Convolution using FFT is alleged to be O(n log(n))... *part of this is things I can't easily find in the FFTW docs. 1) The product of a DFT from FFTW is of the same length as the original PCM stream to which the DFT was applied. 2) "Multiplying" two DFT of length n and m seems to take exactly the same amount of compute power ( O(n*m) ) as calculating the convolution by definition. What am I missing? -- Les Cargill
Convolution and FFTW question.
Started by ●May 30, 2010
Reply by ●May 30, 20102010-05-30
On May 30, 9:20�am, Les Cargill <lcargil...@yahoo.com> wrote:> Seems dumb*, but what the hey: > (data sets are 1D PCM audio data) > > Convolution is O(n*m) where n is the length of one vector to be > convolved, m is the length of the other vector. Convolution > using FFT is alleged to be O(n log(n))... > > *part of this is things I can't easily find in the FFTW docs. > > 1) The product of a DFT from FFTW is of the same length as the > original PCM stream to which the DFT was applied. > > 2) "Multiplying" two DFT of length n and m seems to take exactly > the same amount of compute power ( O(n*m) ) as calculating the > convolution by definition. > > What am I missing? > > -- > Les CargillTake a look at the example in The Scientist and Engineer's Guide to Digital Signal Processing By Steven W. Smith, Ph.D. at http://www.dspguide.com/ch18/1.htm Dale B. Dalrymple
Reply by ●May 30, 20102010-05-30
On 30 Mai, 18:20, Les Cargill <lcargil...@yahoo.com> wrote:> Seems dumb*, but what the hey: > (data sets are 1D PCM audio data) > > Convolution is O(n*m) where n is the length of one vector to be > convolved, m is the length of the other vector. Convolution > using FFT is alleged to be O(n log(n))... > > *part of this is things I can't easily find in the FFTW docs. > > 1) The product of a DFT from FFTW is of the same length as the > original PCM stream to which the DFT was applied. > > 2) "Multiplying" two DFT of length n and m seems to take exactly > the same amount of compute power ( O(n*m) ) as calculating the > convolution by definition. > > What am I missing?You have made a wromg turn somewhere. Assume you want to convolve one M-length sequence with a N-length sequence. Then: - The direct implementation of convolution is O(M*N) - The FFTs will be O(KlogK) where K = M+N - The frequency-domain multiply will be O(M+N) Rune
Reply by ●May 30, 20102010-05-30
dbd wrote:> On May 30, 9:20 am, Les Cargill<lcargil...@yahoo.com> wrote: >> Seems dumb*, but what the hey: >> (data sets are 1D PCM audio data) >> >> Convolution is O(n*m) where n is the length of one vector to be >> convolved, m is the length of the other vector. Convolution >> using FFT is alleged to be O(n log(n))... >> >> *part of this is things I can't easily find in the FFTW docs. >> >> 1) The product of a DFT from FFTW is of the same length as the >> original PCM stream to which the DFT was applied. >> >> 2) "Multiplying" two DFT of length n and m seems to take exactly >> the same amount of compute power ( O(n*m) ) as calculating the >> convolution by definition. >> >> What am I missing? >> >> -- >> Les Cargill > > Take a look at the example in > > The Scientist and Engineer's Guide to Digital Signal Processing > By Steven W. Smith, Ph.D. > > at > > http://www.dspguide.com/ch18/1.htm > > Dale B. DalrympleBeautiful! Thanks much. -- Les Cargill
Reply by ●June 24, 20102010-06-24
Rune Allnor wrote:> On 30 Mai, 18:20, Les Cargill<lcargil...@yahoo.com> wrote: >> Seems dumb*, but what the hey: >> (data sets are 1D PCM audio data) >> >> Convolution is O(n*m) where n is the length of one vector to be >> convolved, m is the length of the other vector. Convolution >> using FFT is alleged to be O(n log(n))... >> >> *part of this is things I can't easily find in the FFTW docs. >> >> 1) The product of a DFT from FFTW is of the same length as the >> original PCM stream to which the DFT was applied. >> >> 2) "Multiplying" two DFT of length n and m seems to take exactly >> the same amount of compute power ( O(n*m) ) as calculating the >> convolution by definition. >> >> What am I missing? > > You have made a wromg turn somewhere. > > Assume you want to convolve one M-length sequence with a > N-length sequence. Then: > > - The direct implementation of convolution is O(M*N) > - The FFTs will be O(KlogK) where K = M+N > - The frequency-domain multiply will be O(M+N) > > RuneWhat sort of transform is this "frequency domain multiply"? It's not a dot product; it's not a cross product. It's not a pointwise multiply*. What is it? *I mean when I take small 2 to 4 sample vectors, convolve them by the definition ( the O(N+M) multiply of the original sample data ) and then take the DFT of the signal & kernel, and of the convolution result, it does not turn out to match what a pointwise multiply would produce Maybe I'm doing it wrong, or I'm not recognizing the result properly. -- Les Cargill -- Les Cargill
Reply by ●June 24, 20102010-06-24
On Jun 24, 10:02 am, Les Cargill <lcargil...@yahoo.com> wrote:> Rune Allnor wrote: > > On 30 Mai, 18:20, Les Cargill<lcargil...@yahoo.com> wrote: > >> Seems dumb*, but what the hey: > >> (data sets are 1D PCM audio data) > > >> Convolution is O(n*m) where n is the length of one vector to be > >> convolved, m is the length of the other vector. Convolution > >> using FFT is alleged to be O(n log(n))... > > >> *part of this is things I can't easily find in the FFTW docs. > > >> 1) The product of a DFT from FFTW is of the same length as the > >> original PCM stream to which the DFT was applied. > > >> 2) "Multiplying" two DFT of length n and m seems to take exactly > >> the same amount of compute power ( O(n*m) ) as calculating the > >> convolution by definition. > > >> What am I missing? > > > You have made a wromg turn somewhere. > > > Assume you want to convolve one M-length sequence with a > > N-length sequence. Then: > > > - The direct implementation of convolution is O(M*N) > > - The FFTs will be O(KlogK) where K = M+N > > - The frequency-domain multiply will be O(M+N) > > > Rune > > What sort of transform is this "frequency domain multiply"? > It's not a dot product; it's not a cross product. It's > not a pointwise multiply*. What is it? > > *I mean when I take small 2 to 4 sample vectors, convolve > them by the definition ( the O(N+M) multiply of the original > sample data ) and then take the DFT of the signal & kernel, > and of the convolution result, it does not turn out to match > what a pointwise multiply would produce > > Maybe I'm doing it wrong, or I'm not recognizing the > result properly. > > -- > Les Cargill > > -- > Les CargillYou do want a pointwise complex multiply. Your confusion comes from a subtlety of the DFT convolution property: multiplication in the frequency domain is equivalent to *circular* convolution in the time domain. This is not the same as what is typically just termed convolution, which is linear convolution. There are techniques to implement linear convolution using FFTs (overlap-save, overlap-add), but if you just do what you noted above, then you will get a vector representing the circular convolution of the two input vectors. Jason
Reply by ●June 24, 20102010-06-24
Jason wrote:> On Jun 24, 10:02 am, Les Cargill<lcargil...@yahoo.com> wrote: >> Rune Allnor wrote: >>> On 30 Mai, 18:20, Les Cargill<lcargil...@yahoo.com> wrote: >>>> Seems dumb*, but what the hey: >>>> (data sets are 1D PCM audio data) >> >>>> Convolution is O(n*m) where n is the length of one vector to be >>>> convolved, m is the length of the other vector. Convolution >>>> using FFT is alleged to be O(n log(n))... >> >>>> *part of this is things I can't easily find in the FFTW docs. >> >>>> 1) The product of a DFT from FFTW is of the same length as the >>>> original PCM stream to which the DFT was applied. >> >>>> 2) "Multiplying" two DFT of length n and m seems to take exactly >>>> the same amount of compute power ( O(n*m) ) as calculating the >>>> convolution by definition. >> >>>> What am I missing? >> >>> You have made a wromg turn somewhere. >> >>> Assume you want to convolve one M-length sequence with a >>> N-length sequence. Then: >> >>> - The direct implementation of convolution is O(M*N) >>> - The FFTs will be O(KlogK) where K = M+N >>> - The frequency-domain multiply will be O(M+N) >> >>> Rune >> >> What sort of transform is this "frequency domain multiply"? >> It's not a dot product; it's not a cross product. It's >> not a pointwise multiply*. What is it? >> >> *I mean when I take small 2 to 4 sample vectors, convolve >> them by the definition ( the O(N+M) multiply of the original >> sample data ) and then take the DFT of the signal& kernel, >> and of the convolution result, it does not turn out to match >> what a pointwise multiply would produce >> >> Maybe I'm doing it wrong, or I'm not recognizing the >> result properly. >> >> -- >> Les Cargill >> >> -- >> Les Cargill > > You do want a pointwise complex multiply. Your confusion comes from a > subtlety of the DFT convolution property: multiplication in the > frequency domain is equivalent to *circular* convolution in the time > domain. This is not the same as what is typically just termed > convolution, which is linear convolution. There are techniques to > implement linear convolution using FFTs (overlap-save, overlap-add), > but if you just do what you noted above, then you will get a vector > representing the circular convolution of the two input vectors. > > JasonThanks, Jason - for some reason, I thought the overlap-add method as Dale pointed me to was for the "by definition" convolution, not for the multiplication of DFTs. -- Les Cargill
Reply by ●June 24, 20102010-06-24
On Jun 24, 9:15�am, Les Cargill <lcargil...@yahoo.com> wrote: ...> Thanks, Jason - for some reason, I thought the overlap-add > method as Dale pointed me to was for the "by definition" > convolution, not for the multiplication of DFTs. > > -- > Les CargillThe overlap-add method is used to perform linear convolutions by people who understand that the required dft size must be at least N + M -1 to give a linear convolution of an N length with an M length vector. Zero fill is used to convert the N and M length vectors to the required size before the forward dft's. Dale B. Dalrymple
Reply by ●June 25, 20102010-06-25
dbd wrote:> On Jun 24, 9:15 am, Les Cargill<lcargil...@yahoo.com> wrote: > ... >> Thanks, Jason - for some reason, I thought the overlap-add >> method as Dale pointed me to was for the "by definition" >> convolution, not for the multiplication of DFTs. >> >> -- >> Les Cargill > > The overlap-add method is used to perform linear convolutions by > people who understand that the required dft size must be at least N + > M -1 to give a linear convolution of an N length with an M length > vector.I'm reasonably sure I got that part....> Zero fill is used to convert the N and M length vectors to the > required size before the forward dft's. >Right.> Dale B. Dalrymple-- Les Cargill
