bellda2005@cox.net wrote:> 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?Half of a symmetric result suffices, I think. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Convolution of symmetric data
Started by ●May 21, 2009
Reply by ●May 22, 20092009-05-22
Reply by ●May 22, 20092009-05-22
On May 22, 3:39�pm, Jerry Avins <j...@ieee.org> wrote:> bellda2...@cox.net wrote: > > 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? > > Half of a symmetric result suffices, I think. > > Jerry > -- > Engineering is the art of making what you want from things you can get. > �����������������������������������������������������������������������- Hide quoted text - > > - Show quoted text -If only one of the sequences is symmetric, the resulting convolution will not be symmetric. It takes both being symmetric to get the symmetric output so you can get the complete result while only completely computing about half of the results. Dirk
Reply by ●May 22, 20092009-05-22
bellda2005@cox.net wrote:> On May 22, 3:39 pm, Jerry Avins <j...@ieee.org> wrote: >> bellda2...@cox.net wrote: >>> 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 account 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? >> Half of a symmetric result suffices, I think. >> >> Jerry >> -- >> Engineering is the art of making what you want from things you can get. >> �����������������������������������������������������������������������- Hide quoted text - >> >> - Show quoted text - > > If only one of the sequences is symmetric, the resulting convolution > will not be symmetric. It takes both being symmetric to get the > symmetric output so you can get the complete result while only > completely computing about half of the results.I wrote "With convolution that otherwise takes no account of being *doubly* symmetric, one can still stop halfway through." By /otherwise/, I meant not modifying the computation. but also not forgetting the double symmetry. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●May 23, 20092009-05-23
On May 22, 7:59�pm, Jerry Avins <j...@ieee.org> wrote:> bellda2...@cox.net wrote: > > On May 22, 3:39 pm, Jerry Avins <j...@ieee.org> wrote: > >> bellda2...@cox.net wrote: > >>> 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 account 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? > >> Half of a symmetric result suffices, I think. > > >> Jerry > >> -- > >> Engineering is the art of making what you want from things you can get. > >> �����������������������������������������������������������������������- Hide quoted text - > > >> - Show quoted text - > > > If only one of the sequences is symmetric, the resulting convolution > > will not be symmetric. �It takes both being symmetric to get the > > symmetric output so you can get the complete result while only > > completely computing about half of the results. > > � I wrote "With convolution that otherwise takes no account of being > *doubly* symmetric, one can still stop halfway through." > > By /otherwise/, I meant not modifying the computation. but also not > forgetting the double symmetry. > > Jerry > -- > Engineering is the art of making what you want from things you can get. > �����������������������������������������������������������������������- Hide quoted text - > > - Show quoted text -Got it. Agreed. Dirk
Reply by ●May 24, 20092009-05-24
>On May 22, 7:59=A0pm, Jerry Avins <j...@ieee.org> wrote: >> bellda2...@cox.net wrote: >> > On May 22, 3:39 pm, Jerry Avins <j...@ieee.org> wrote: >> >> bellda2...@cox.net wrote: >> >>> 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 andso=>me >> >>>>>>>> overhead. If your processor has a hardware multiplier, thatwill>> >>>>>>>> probably slow the calculation. >> >>>>>>> That's not correct. =A0Using symmetry (if done properly) canyou =>a >> >>>>>>> factor of 2 in the number of multiplications and asymptoticallya>> >>>>>>> factor of 2 in the number of additions, and a roughly a factorof=> 2 in >> >>>>>>> memory compared to an FFT for real data. =A0 An FFT specializedf=>or real- >> >>>>>>> symmetric data is otherwise known as a fast discrete cosinetrans=>form >> >>>>>>> (DCT). >> >>>>>>> The trick is that you have to arrange your data so that thesymme=>try >> >>>>>>> is in the right form for a DCT, and there are 8 types of DCT >> >>>>>>> corresponding to 8 different symmetries. =A0Wikipedia as a DCTar=>ticle >> >>>>>>> with a figure that should help explain the different optionsyou =>have >> >>>>>>> for the symmetry: >> >>>>>>> =A0 =A0http://en.wikipedia.org/wiki/Discrete_cosine_transform >> >>>>>>> The original poster has symmetry that corresponds to a DCT-II,wh=>ich >> >>>>>>> is why it is not giving the same result when he replaces itwith =>the >> >>>>>>> symmetry corresponding to a DCT-I. =A0(Both DCT I and II aresupp=>orted >> >>>>>>> in FFTW.) >> >>>>>> Thanks for putting me straight. It occurred to me only thismornin=>g that >> >>>>>> the additions needed to combine the symmetric coefficients arerec=>overed >> >>>>>> =A0 in the accumulation. How are the rest of the additionssaved?>> >>>>>> Jerry >> >>>>>> -- >> >>>>>> Engineering is the art of making what you want from things youcan=> get. >> >>>>>>=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=>=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF= >=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF-H=>ide quoted text - >> >>>>>> - Show quoted text - >> >>>>> For time domain convolution with one of the sequences beingsymmetr=>ic, >> >>>>> you save half (or half-1 if length of symmetric sequence is odd)th=>e >> >>>>> 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 andabou=>t a >> >>>>> quarter of the original multiplies. >> >>>> Thanks. With convolution that otherwise takes no account of being >> >>>> doubly symmetric, one can still stop halfway through. >> >>>> Jerry >> >>>> -- >> >>>> Engineering is the art of making what you want from things you cang=>et. >> >>>>=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=>=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF= >=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF-H=>ide quoted text - >> >>>> - Show quoted text - >> >>> Do you mean and still get the complete result? >> >> Half of a symmetric result suffices, I think. >> >> >> Jerry >> >> -- >> >> Engineering is the art of making what you want from things you canget=>. >> >>=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=>=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF= >=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF-Hide=> quoted text - >> >> >> - Show quoted text - >> >> > If only one of the sequences is symmetric, the resulting convolution >> > will not be symmetric. =A0It takes both being symmetric to get the >> > symmetric output so you can get the complete result while only >> > completely computing about half of the results. >> >> =A0 I wrote "With convolution that otherwise takes no account of being >> *doubly* symmetric, one can still stop halfway through." >> >> By /otherwise/, I meant not modifying the computation. but also not >> forgetting the double symmetry. >> >> Jerry >> -- >> Engineering is the art of making what you want from things you canget.>>=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=>=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF= >=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF=AF- Hidequ=>oted text - >> >> - Show quoted text - > >Got it. Agreed. > >Dirk >I am following the discussion and it was of help. From hat I follow is that if my data are symmetric I can stop the convolution halfway through as the result is also symmeric. Specifically take for example : a=[1 2 3 4 3 2 1] or [1 2 3 0 -3 -2 -1] b=[2 4 6 8 6 4 2] or [2 4 6 0 -6 -5 -3] depending on wether a and b are even/odd. Now in finding c=a*b by direct multiplication, I can stop halfway through as I know c will be either odd/even. Now, if I find c by using FFT, c=ifft(fft(a).*fft(b)) (after padding a and b to the size(a,b)*2-a places) there is NO WAY of stopping halfway through (correct me if I am wrong)! Or can I find ONLY HALF of the convolution using FFT? Why I am asking is that I have two convolve 2-D symmetric matrices with only few columns compared to rows and the matrices are SPARSE. Now, if find the convolution using DIRECT MULTIPLICATION but carefully selecting only the non-zero component (as there will be lot of zeros) and only half of the result (due to odd/even symmetry), it becomes faster than find the convolution by FFT (after zero padding though) as in FFT I neither have any option of selecting only the non-zero component nor only the half of the data (to use the symmetry). So, my question is that is there a way to make the FFT convolution faster or it's still advantageous to use direct multiplication?
Reply by ●May 25, 20092009-05-25
On May 23, 11:21�pm, "mpb" <madhurjyap.b...@gmail.com> wrote:> Why I am asking is that I have two convolve 2-D symmetric matrices with > only few columns compared to rows and the matrices are SPARSE. Now, if find > the convolution using DIRECT MULTIPLICATION but carefully selecting only > the non-zero component (as there will be lot of zeros) and only half of the > result (due to odd/even symmetry), it becomes faster than find the > convolution by FFT (after zero padding though) as in FFT I neither have any > option of selecting only the non-zero component nor only the half of the > data (to use the symmetry).You have two separate questions here. First, can you take advantage of symmetry in an FFT? Yes, and the result is a fast discrete cosine transform, which only computes the non-redundant parts of the transform and saves roughly a factor of 2 compared to nonsymmetric data. Second, can you take advantage of some arbitrary sparsity in your data? Yes, this is called a "pruned FFT" (google it), but the gains in general are much smaller; it depends a lot on how much sparsity you have. Steven
Reply by ●May 25, 20092009-05-25
>On May 23, 11:21=A0pm, "mpb" <madhurjyap.b...@gmail.com> wrote: >> Why I am asking is that I have two convolve 2-D symmetric matriceswith>> only few columns compared to rows and the matrices are SPARSE. Now, iffi=>nd >> the convolution using DIRECT MULTIPLICATION but carefully selectingonly>> the non-zero component (as there will be lot of zeros) and only half oft=>he >> result (due to odd/even symmetry), it becomes faster than find the >> convolution by FFT (after zero padding though) as in FFT I neither havea=>ny >> option of selecting only the non-zero component nor only the half ofthe>> data (to use the symmetry). > >You have two separate questions here. > >First, can you take advantage of symmetry in an FFT? Yes, and the >result is a fast discrete cosine transform, which only computes the >non-redundant parts of the transform and saves roughly a factor of 2 >compared to nonsymmetric data. > >Second, can you take advantage of some arbitrary sparsity in your >data? Yes, this is called a "pruned FFT" (google it), but the gains >in general are much smaller; it depends a lot on how much sparsity you >have. > >Steven >Yes, you're right. I am just thinking the ways to make the convolution faster : (i) by using the symmetry either by using DST or DCT and (ii) by using non-redundant component of the FFT (pruned FFT) However, pruned FFT may not yield much (but I have 2-d convolution, so it might). Then I was planning to use FFTW or DCT ad DST, but the FFTW does then DST/DCT by pre- and post-processing FFT, not a pure DST/DCT, so it's actually slower than doing FFT. Can you suggest any DST/DCT (2-D) routines, which natively computes the DST/DCT? The time factor is very serious in my case as I am finding these convolutions as a part of a simulation, which will probably evaluate these convolution some million times. So saving time, if it can be, worth trying. I have not yet tried pruned FFT though! ---Madhurjya
Reply by ●May 25, 20092009-05-25
On May 25, 7:34 am, "mpb" <madhurjyap.b...@gmail.com> wrote:> ... > but the FFTW does > then DST/DCT by pre- and post-processing FFT, not a pure DST/DCT, so it's > actually slower than doing FFT. > ... > ---MadhurjyaThe size of the FFT performed inside the DCT implementation is smaller than the original symmetric data set. It processes only a non- redundant subset of the original data and is therefore faster than a direct FFT on the symmetric data set despite the pre- and post- processing. Dale B. Dalrymple
Reply by ●May 25, 20092009-05-25
mpb schrieb:> 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]How large are your vectors? I would assume that an optimized (SIMD) direct convolution is faster than black magic based on FFTW if the vector size is smaller than ~50. The result will also be symmetric, so you would only need to calculate one half of it. Hendrik vdH
