MathGroup Archive 1999

[Date Index] [Thread Index] [Author Index]

Search the Archive

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



  • Prev by Date: Re: Discrete Convolution
  • Next by Date: Re: Discrete Convolution
  • Previous by thread: Re: Discrete Convolution
  • Next by thread: Re: Discrete Convolution