Discrete Convolution
- To: mathgroup at smc.vnet.net
- Subject: [mg18943] Discrete Convolution
- From: "Alister McAlister" <alisterq at psy.uwa.edu.au>
- Date: Fri, 30 Jul 1999 01:33:39 -0400
- Organization: The University of Western Australia
- Sender: owner-wri-mathgroup at wolfram.com
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])