Discrete Convolution

[Alister McAlister]

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

[Jens-Peer Kuska]

Hi Alister,

In[1]:=
?ListConvolve

"ListConvolve[ker, list] forms the convolution of the kernel ker with
list. \
ListConvolve[ker, list, k] forms the cyclic convolution in which the kth
\
element of ker is aligned with each element in list. ListConvolve[ker,
list, \
{kL, kR}] forms the cyclic convolution whose first element contains
list[[1]] \
ker[[kL]] and whose last element contains list[[-1]] ker[[kR]]. \
ListConvolve[ker, list, klist, p] forms the convolution in which list is
\
padded at each end with repetitions of the element p. ListConvolve[ker,
list, \
klist, {p1, p2, ... }] forms the convolution in which list is padded at
each \
end with cyclic repetitions of the pi. ListConvolve[ker, list, klist, \
padding, g, h] forms a generalized convolution in which g is used in
place of \
Times and h in place of Plus. ListConvolve[ker, list, klist, padding, g,
h, \
lev] forms a convolution using elements at level lev in ker and list."

in Mathematica 4.0

Hope that helps
Jens

[Allan Hayes]

Alister:
The new Version 4.x functions, ListConvolve and ListCorrelate look like
meeting your needs.
For example

ListConvolve[{a0, a1, a2}, {b0, b1, b2}, {1, 3}, 0]

{a0 b0, a1 b0 + a0 b1, a2 b0 + a1 b1 + a0 b2, a2 b1 + a1 b2, a2 b2}

There is a lot more to these functions - the full HelpBrowser information
needs to be consulted, but here is the shorter informatiion:

?ListConvolve

"ListConvolve[ker, list] forms the convolution of the kernel ker with list.
\
ListConvolve[ker, list, k] forms the cyclic convolution in which the kth \
element of ker is aligned with each element in list. ListConvolve[ker, list,
\
{kL, kR}] forms the cyclic convolution whose first element contains
list[[1]] \
ker[[kL]] and whose last element contains list[[-1]] ker[[kR]]. \
ListConvolve[ker, list, klist, p] forms the convolution in which list is \
padded at each end with repetitions of the element p. ListConvolve[ker,
list, \
klist, {p1, p2, ... }] forms the convolution in which list is padded at each
\
end with cyclic repetitions of the pi. ListConvolve[ker, list, klist, \
padding, g, h] forms a generalized convolution in which g is used in place
of \
Times and h in place of Plus. ListConvolve[ker, list, klist, padding, g, h,
\
lev] forms a convolution using elements at level lev in ker and list."

Allan
---------------------
Allan Hayes
Mathematica Training and Consulting
Leicester UK
www.haystack.demon.co.uk
h...@haystack.demon.co.uk
Voice: +44 (0)116 271 4198
Fax: +44 (0)870 164 0565

Alister McAlister <alis...@psy.uwa.edu.au> wrote in message
news:7nrddv$i...@smc.vnet.net...

> 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

[Bruno Daniel]

Hi Alister

Why not just the direct implementation?

\!\(Conv[a_List, b_List] :=
Module[\n\t\t{la = Length[a], lb = Length[b]}, \n\t\t
Table[\[Sum]\+\(i = Max[1, k - la]\)\%\(Min[lb, k - 1]\)a
\[LeftDoubleBracket]k - i\[RightDoubleBracket]
b\[LeftDoubleBracket]i\[RightDoubleBracket], {k, 2, la + lb}]]\)

or expressed in InputForm:

Conv[a_List, b_List] :=
Module[{la = Length[a], lb = Length[b]},
Table[Sum[a[[k - i]]*b[[i]],
{i, Max[1, k - la], Min[lb, k - 1]}], {k, 2, la + lb}]]

Example:
In[40]:=Conv[{a,b,c},{e,f}]
Out[40]= {a e, b e + a f, c e + b f, c f}

Yours sincerely
Bruno

[Dave Harvatin]

Mark,

Have a look at the HankelMatrix command in the package
LinearAlgebra`MatrixManipulation`. You should be able to manipulate your
data so that the the convolution of list x with list y can be represented by
the dot product of a vector formed from list x with a Hankel matrix formed
from list y (or perhaps list y in reverse order). I hope this helps.

Dave Harvatin