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
```
Reply by June 24, 20102010-06-24
```On Jun 24, 9:15&#2013266080;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. 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 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.
>
> Jason

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
```
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 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.

Jason
```
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)
>
> 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

```
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. Dalrymple

Beautiful! Thanks much.

--
Les Cargill
```
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
```On May 30, 9:20&#2013266080;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. Dalrymple
```
Reply by May 30, 20102010-05-30
```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
```