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