Hi All! I have to convolute two sets of symmetric data which are zero centered i.e. c=a*b where for example a=[1 2 3 4 5 4 3 2 1] b=[2 4 6 8 10 8 6 4 2] The data may be also odd a=[5 4 3 2 0 -2 -3 -4 -5] etc. etc. I can perform the convolution either by FFT or by direct multiplication. But I want to make use of the odd/even symmetry of the data. If I want to use FFTW, it requires the DC component as 1st element of the array i.e. for making use of the symmetry I need to make the data as a1=[5 4 3 2 1 2 3 4] and b1=[10 8 6 4 2 4 6 8] and so on. But the convolutions of the two c=conv(a,b) is not same as c1=conv(a1,b1). How do I make use of the symmetry? Best, --- Madhurjya
Convolution of symmetric data
Started by ●May 21, 2009
Reply by ●May 21, 20092009-05-21
mpb wrote:> Hi All! > > I have to convolute two sets of symmetric data which are zero centered > i.e. > > c=a*b where for example > > a=[1 2 3 4 5 4 3 2 1] > > b=[2 4 6 8 10 8 6 4 2] > > The data may be also odd > > a=[5 4 3 2 0 -2 -3 -4 -5] etc. etc. > > I can perform the convolution either by FFT or by direct multiplication. > But I want to make use of the odd/even symmetry of the data. If I want to > use FFTW, it requires the DC component as 1st element of the array i.e. > for > making use of the symmetry I need to make the data as > > a1=[5 4 3 2 1 2 3 4] and > > b1=[10 8 6 4 2 4 6 8] and so on. > > But the convolutions of the two c=conv(a,b) is not same as > c1=conv(a1,b1). > > How do I make use of the symmetry? Best,Using symmetry replaces a multiplication with an addition and some overhead. If your processor has a hardware multiplier, that will probably slow the calculation. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●May 21, 20092009-05-21
mpb wrote:> Hi All! >.........>> I can perform the convolution either by FFT or by direct > multiplication........... I don't think you mean that... I think you mean you can convolve directly in the time domain OR By FFT *AND* multiplication AND IFFT. ********************* Might I suggest that you slow down and split this up into two parts at least: 1) You can't convolve the arrays you provide here using an FFT. They have to be of length at least M+N-1 or 9+9-1=17 like this: a=[1 2 3 4 5 4 3 2 1 0 0 0 0 0 0 0 0] b=[2 4 6 8 10 8 6 4 2 0 0 0 0 0 0 0 0] 2) Then you can manipulate these to meet some alignment criteria you may have as in: a=[5 4 3 2 1 0 0 0 0 0 0 0 0 1 2 3 4] b=[10 8 6 4 2 0 0 0 0 0 0 0 0 2 4 6 8] What this step does is to make the arrays purely even symmetry for the FFT. But that's all. 3) "Take advantage of the symmetry" is still an open question here. Hint: The FFTs of these latter sequences will be purely real. Fred
Reply by ●May 21, 20092009-05-21
>mpb wrote: >> Hi All! >> >.........> >> I can perform the convolution either by FFT or by direct >> multiplication. >.......... > >I don't think you mean that... > >I think you mean you can convolve directly in the time domain > >OR > >By FFT *AND* multiplication AND IFFT. > >********************* > >Might I suggest that you slow down and split this up into two parts at >least: > >1) You can't convolve the arrays you provide here using an FFT. Theyhave>to be of length at least M+N-1 or 9+9-1=17 like this: > >a=[1 2 3 4 5 4 3 2 1 0 0 0 0 0 0 0 0] > >b=[2 4 6 8 10 8 6 4 2 0 0 0 0 0 0 0 0] > >2) Then you can manipulate these to meet some alignment criteria you may>have as in: > >a=[5 4 3 2 1 0 0 0 0 0 0 0 0 1 2 3 4] > >b=[10 8 6 4 2 0 0 0 0 0 0 0 0 2 4 6 8] > >What this step does is to make the arrays purely even symmetry for theFFT.>But that's all. > >3) "Take advantage of the symmetry" is still an open question here. > >Hint: The FFTs of these latter sequences will be purely real. > >Fred > > >Thanks for the suggestions. Let me be a bit clear. The case here is that I have an equation in real space e.g. dX/dt = A x B + .... (x means multiplication) When I Fourier transform this equation I have something like FT(dX/dt) = a*b + .... where a=FT(A) and b=FT(B) and the * means convolution. This is standard as FT of multiplication becomes convolution in Fourier domain. Now, I want to evaluate this convolution in Fourier domain using FFT. As the original data A and B have odd/even symmetry, a and b are purely real and have odd/even symmetry too (zero centered) which are the arrays I mentioned earlier. Now makeing use of the symmetry I meant that can I use DST or DCT instead of FFT to evaluate the convolution. But as I understand convolution using DST or DCT is not that straight forward. So, I could probably use DCT/DST to find the FT of a and b and then do a simple multiplication following the convolution theorem. Appreciate any help! --- Madhurjya
Reply by ●May 22, 20092009-05-22
On May 21, 11:38�am, Jerry Avins <j...@ieee.org> wrote:> Using symmetry replaces a multiplication with an addition and some > overhead. If your processor has a hardware multiplier, that will > probably slow the calculation.That's not correct. Using symmetry (if done properly) can you a factor of 2 in the number of multiplications and asymptotically a factor of 2 in the number of additions, and a roughly a factor of 2 in memory compared to an FFT for real data. An FFT specialized for real- symmetric data is otherwise known as a fast discrete cosine transform (DCT). The trick is that you have to arrange your data so that the symmetry is in the right form for a DCT, and there are 8 types of DCT corresponding to 8 different symmetries. Wikipedia as a DCT article with a figure that should help explain the different options you have for the symmetry: http://en.wikipedia.org/wiki/Discrete_cosine_transform The original poster has symmetry that corresponds to a DCT-II, which is why it is not giving the same result when he replaces it with the symmetry corresponding to a DCT-I. (Both DCT I and II are supported in FFTW.) Regards, Steven G. Johnson
Reply by ●May 22, 20092009-05-22
Steven G. Johnson wrote:> On May 21, 11:38 am, Jerry Avins <j...@ieee.org> wrote: >> Using symmetry replaces a multiplication with an addition and some >> overhead. If your processor has a hardware multiplier, that will >> probably slow the calculation. > > That's not correct. Using symmetry (if done properly) can you a > factor of 2 in the number of multiplications and asymptotically a > factor of 2 in the number of additions, and a roughly a factor of 2 in > memory compared to an FFT for real data. An FFT specialized for real- > symmetric data is otherwise known as a fast discrete cosine transform > (DCT). > > The trick is that you have to arrange your data so that the symmetry > is in the right form for a DCT, and there are 8 types of DCT > corresponding to 8 different symmetries. Wikipedia as a DCT article > with a figure that should help explain the different options you have > for the symmetry: > > http://en.wikipedia.org/wiki/Discrete_cosine_transform > > The original poster has symmetry that corresponds to a DCT-II, which > is why it is not giving the same result when he replaces it with the > symmetry corresponding to a DCT-I. (Both DCT I and II are supported > in FFTW.)Thanks for putting me straight. It occurred to me only this morning that the additions needed to combine the symmetric coefficients are recovered in the accumulation. How are the rest of the additions saved? Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●May 22, 20092009-05-22
On May 22, 1:51�pm, Jerry Avins <j...@ieee.org> wrote:> Steven G. Johnson wrote: > > On May 21, 11:38 am, Jerry Avins <j...@ieee.org> wrote: > >> Using symmetry replaces a multiplication with an addition and some > >> overhead. If your processor has a hardware multiplier, that will > >> probably slow the calculation. > > > That's not correct. �Using symmetry (if done properly) can you a > > factor of 2 in the number of multiplications and asymptotically a > > factor of 2 in the number of additions, and a roughly a factor of 2 in > > memory compared to an FFT for real data. � An FFT specialized for real- > > symmetric data is otherwise known as a fast discrete cosine transform > > (DCT). > > > The trick is that you have to arrange your data so that the symmetry > > is in the right form for a DCT, and there are 8 types of DCT > > corresponding to 8 different symmetries. �Wikipedia as a DCT article > > with a figure that should help explain the different options you have > > for the symmetry: > > > � �http://en.wikipedia.org/wiki/Discrete_cosine_transform > > > The original poster has symmetry that corresponds to a DCT-II, which > > is why it is not giving the same result when he replaces it with the > > symmetry corresponding to a DCT-I. �(Both DCT I and II are supported > > in FFTW.) > > Thanks for putting me straight. It occurred to me only this morning that > the additions needed to combine the symmetric coefficients are recovered > � in the accumulation. How are the rest of the additions saved? > > Jerry > -- > Engineering is the art of making what you want from things you can get. > �����������������������������������������������������������������������- Hide quoted text - > > - Show quoted text -Seems like for time domain convolution the savings is not approximately one half, but approximately three quarters, because the convolution of two symmetric sequences is itself symmetric, so only half (or half+1) of the output values actually need to be computed. Dirk
Reply by ●May 22, 20092009-05-22
On May 22, 1:51�pm, Jerry Avins <j...@ieee.org> wrote:> Steven G. Johnson wrote: > > On May 21, 11:38 am, Jerry Avins <j...@ieee.org> wrote: > >> Using symmetry replaces a multiplication with an addition and some > >> overhead. If your processor has a hardware multiplier, that will > >> probably slow the calculation. > > > That's not correct. �Using symmetry (if done properly) can you a > > factor of 2 in the number of multiplications and asymptotically a > > factor of 2 in the number of additions, and a roughly a factor of 2 in > > memory compared to an FFT for real data. � An FFT specialized for real- > > symmetric data is otherwise known as a fast discrete cosine transform > > (DCT). > > > The trick is that you have to arrange your data so that the symmetry > > is in the right form for a DCT, and there are 8 types of DCT > > corresponding to 8 different symmetries. �Wikipedia as a DCT article > > with a figure that should help explain the different options you have > > for the symmetry: > > > � �http://en.wikipedia.org/wiki/Discrete_cosine_transform > > > The original poster has symmetry that corresponds to a DCT-II, which > > is why it is not giving the same result when he replaces it with the > > symmetry corresponding to a DCT-I. �(Both DCT I and II are supported > > in FFTW.) > > Thanks for putting me straight. It occurred to me only this morning that > the additions needed to combine the symmetric coefficients are recovered > � in the accumulation. How are the rest of the additions saved? > > Jerry > -- > Engineering is the art of making what you want from things you can get. > �����������������������������������������������������������������������- Hide quoted text - > > - Show quoted text -For time domain convolution with one of the sequences being symmetric, you save half (or half-1 if length of symmetric sequence is odd) the multiplies and save none of the adds. If both of the sequences are symmetric then the output of the convolution is also symmetric, so the second half need not be computed, and you end up with about half the original adds and about a quarter of the original multiplies. Dirk
Reply by ●May 22, 20092009-05-22
bellda2005@cox.net wrote:> On May 22, 1:51 pm, Jerry Avins <j...@ieee.org> wrote: >> Steven G. Johnson wrote: >>> On May 21, 11:38 am, Jerry Avins <j...@ieee.org> wrote: >>>> Using symmetry replaces a multiplication with an addition and some >>>> overhead. If your processor has a hardware multiplier, that will >>>> probably slow the calculation. >>> That's not correct. Using symmetry (if done properly) can you a >>> factor of 2 in the number of multiplications and asymptotically a >>> factor of 2 in the number of additions, and a roughly a factor of 2 in >>> memory compared to an FFT for real data. An FFT specialized for real- >>> symmetric data is otherwise known as a fast discrete cosine transform >>> (DCT). >>> The trick is that you have to arrange your data so that the symmetry >>> is in the right form for a DCT, and there are 8 types of DCT >>> corresponding to 8 different symmetries. Wikipedia as a DCT article >>> with a figure that should help explain the different options you have >>> for the symmetry: >>> http://en.wikipedia.org/wiki/Discrete_cosine_transform >>> The original poster has symmetry that corresponds to a DCT-II, which >>> is why it is not giving the same result when he replaces it with the >>> symmetry corresponding to a DCT-I. (Both DCT I and II are supported >>> in FFTW.) >> Thanks for putting me straight. It occurred to me only this morning that >> the additions needed to combine the symmetric coefficients are recovered >> in the accumulation. How are the rest of the additions saved? >> >> Jerry >> -- >> Engineering is the art of making what you want from things you can get. >> �����������������������������������������������������������������������- Hide quoted text - >> >> - Show quoted text - > > For time domain convolution with one of the sequences being symmetric, > you save half (or half-1 if length of symmetric sequence is odd) the > multiplies and save none of the adds. > > If both of the sequences are symmetric then the output of the > convolution is also symmetric, so the second half need not be > computed, and you end up with about half the original adds and about a > quarter of the original multiplies.Thanks. With convolution that otherwise takes no avccount of being doubly symmetric, one can still stop halfway through. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●May 22, 20092009-05-22
On May 22, 3:00�pm, Jerry Avins <j...@ieee.org> wrote:> bellda2...@cox.net wrote: > > On May 22, 1:51 pm, Jerry Avins <j...@ieee.org> wrote: > >> Steven G. Johnson wrote: > >>> On May 21, 11:38 am, Jerry Avins <j...@ieee.org> wrote: > >>>> Using symmetry replaces a multiplication with an addition and some > >>>> overhead. If your processor has a hardware multiplier, that will > >>>> probably slow the calculation. > >>> That's not correct. �Using symmetry (if done properly) can you a > >>> factor of 2 in the number of multiplications and asymptotically a > >>> factor of 2 in the number of additions, and a roughly a factor of 2 in > >>> memory compared to an FFT for real data. � An FFT specialized for real- > >>> symmetric data is otherwise known as a fast discrete cosine transform > >>> (DCT). > >>> The trick is that you have to arrange your data so that the symmetry > >>> is in the right form for a DCT, and there are 8 types of DCT > >>> corresponding to 8 different symmetries. �Wikipedia as a DCT article > >>> with a figure that should help explain the different options you have > >>> for the symmetry: > >>> � �http://en.wikipedia.org/wiki/Discrete_cosine_transform > >>> The original poster has symmetry that corresponds to a DCT-II, which > >>> is why it is not giving the same result when he replaces it with the > >>> symmetry corresponding to a DCT-I. �(Both DCT I and II are supported > >>> in FFTW.) > >> Thanks for putting me straight. It occurred to me only this morning that > >> the additions needed to combine the symmetric coefficients are recovered > >> � in the accumulation. How are the rest of the additions saved? > > >> Jerry > >> -- > >> Engineering is the art of making what you want from things you can get. > >> �����������������������������������������������������������������������- Hide quoted text - > > >> - Show quoted text - > > > For time domain convolution with one of the sequences being symmetric, > > you save half (or half-1 if length of symmetric sequence is odd) the > > multiplies and save none of the adds. > > > If both of the sequences are symmetric then the output of the > > convolution is also symmetric, so the second half need not be > > computed, and you end up with about half the original adds and about a > > quarter of the original multiplies. > > Thanks. With convolution that otherwise takes no avccount of being > doubly symmetric, one can still stop halfway through. > > Jerry > -- > Engineering is the art of making what you want from things you can get. > �����������������������������������������������������������������������- Hide quoted text - > > - Show quoted text -Do you mean and still get the complete result? Dirk
