Re: Discrete Convolution

*To*: mathgroup at smc.vnet.net*Subject*: [mg19026] Re: [mg18943] Discrete Convolution*From*: "Wolf, Hartmut" <hwolf at debis.com>*Date*: Tue, 3 Aug 1999 13:44:57 -0400*Organization*: debis Systemhaus*References*: <199907300533.BAA18638@smc.vnet.net.>*Sender*: owner-wri-mathgroup at wolfram.com

Hello Mark Alister McAlister schrieb: > > I want a function that mimics Matlab's "conv" function for doing a discrete > convolution of two lists. > > CONV Convolution and polynomial multiplication. > C = CONV(A, B) convolves vectors A and B. The resulting > vector is length LENGTH(A)+LENGTH(B)-1. > If A and B are vectors of polynomial coefficients, convolving > them is equivalent to multiplying the two polynomials. > > I wrote the following, but is there a way of either of > (1) speeding up the code by changing the algorithm ... > ignoring simple things like the multiple evaluations > of Length and so forth which I have left > in only for what I hope is clarity; or > (2) Using a built in function (possibly connected with polynomials) to do > the same thing? > > Mark R Diamond > No spam email: markd at psy dot uwa dot edu dot au > -------------------------------------------------------- > > convolve[a_List,b_List]:=Module[ > { > (* reverse one of the lists prior to the convolution *) > ra=Reverse[a], > > (* A variable that collects the indices of lists ra and b, > respectively *) > (* that will be Dot[ ]-ed together. *) > indices > }, > > (* Create the table of indices *) > indices=Table[ > { > { > Max[Length[a]+1-i,1], > Min[Length[a],Length[a]+Length[b]-i] > }, > { > Max[1,i-Length[a]+1],Min[Length[b],i] > } > }, > {i,Length[a]+Length[b]-1} > ]; > > (* Create a list of the appropriate pairs of dot products *) > Map[(Take[ra,#[[1]] ].Take[ b,#[[2]] ])&, indices] > ] /; (VectorQ[a,NumberQ]\[And]VectorQ[b,NumberQ]) I already replied to your posting, but maybe you want a I different answer. About programming your function, your proposal clearly does it, as you have seen from my first reply. Now in Mathematica 4 there is a function called In[100]:= ?ListConvolve As far as I could see, that function doesn't quite do it (does anyone?). But if you add a little help and define a function T: In[117]:= T[x_, y__] := Times[x, y] In[118]:= T[_] = Sequence[]; then In[119]:= ListConvolve[coeffA, coeffB, {1, -1}, {}, T, Plus] Out[119]= {a[0] b[0], a[1] b[0] + a[0] b[1], a[2] b[0] + a[1] b[1] + a[0] b[2], a[3] b[0] + a[2] b[1] + a[1] b[2] + a[0] b[3], a[4] b[0] + a[3] b[1] + a[2] b[2] + a[1] b[3] + a[0] b[4], a[4] b[1] + a[3] b[2] + a[2] b[3] + a[1] b[4] + a[0] b[5], a[4] b[2] + a[3] b[3] + a[2] b[4] + a[1] b[5] + a[0] b[6], a[4] b[3] + a[3] b[4] + a[2] b[5] + a[1] b[6], a[4] b[4] + a[3] b[5] + a[2] b[6], a[4] b[5] + a[3] b[6], a[4] b[6]} coeffA and coeffB had been: In[2]:= coeffA = Array[a, {5}, {0}] Out[2]= {a[0], a[1], a[2], a[3], a[4]} In[2]:= coeffB = Array[b, {7}, {0}] Out[2]= {b[0], b[1], b[2], b[3], b[4], b[5], b[6]} It also works on numbers: In[124]:= ListConvolve[Range[3], Range[5], {1, -1}, {}, T, Plus] Out[124]= {1, 4, 10, 16, 22, 22, 15} In[126]:= (1 + 2x + 3x^2)(1 + 2x + 3x^2 + 4x^3 + 5x^4) // Expand Out[126]= 1 + 4 x + 10 x^2 + 16 x^3 + 22 x^4 + 22 x^5 + 15 x^6 Kind regards, hw