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])