({{, (RefLink[ListConvolve, paclet:ref/ListConvolve])[ker,list]
forms the convolution of the kernel ker with list. }, {, (RefLink[ListConvolve, paclet:ref/ListConvolve])[ker,list,k]
forms the cyclic convolution in which the k(^th) element of ker is aligned with each element in list. }, {, (RefLink[ListConvolve, paclet:ref/ListConvolve])[ker,list,{(Subscript[k, L]),(Subscript[k, R])}]
forms the cyclic convolution whose first element contains list[[1]]ker[[(Subscript[k, L])]] and whose last element contains list[[-1]]ker[[(Subscript[k, R])]]. }, {, (RefLink[ListConvolve, paclet:ref/ListConvolve])[ker,list,klist,p]
forms the convolution in which list is padded at each end with repetitions of the element p. }, {, (RefLink[ListConvolve, paclet:ref/ListConvolve])[ker,list,klist,{(Subscript[p, 1]),(Subscript[p, 2]),…}]
forms the convolution in which list is padded at each end with cyclic repetitions of the (Subscript[p, i]). }, {, (RefLink[ListConvolve, paclet:ref/ListConvolve])[ker,list,klist,padding,g,h]
forms a generalized convolution in which g is used in place of (RefLink[Times, paclet:ref/Times]) and h in place of (RefLink[Plus, paclet:ref/Plus]). }, {, (RefLink[ListConvolve, paclet:ref/ListConvolve])[ker,list,klist,padding,g,h,lev]
forms a convolution using elements at level lev in ker and list. }})

OpenersNotesSection(Spacer1)Details

With kernel (Subscript[K, r]) and list (Subscript[a, s]), (RefLink[ListConvolve, paclet:ref/ListConvolve])[ker,list] computes (∑_r)(Subscript[K, r])(Subscript[a, s-r]), where the limits of the sum are such that the kernel never overhangs either end of the list.

(RefLink[ListConvolve, paclet:ref/ListConvolve])[ker,list] gives a result of length (RefLink[Length, paclet:ref/Length])[list]-(RefLink[Length, paclet:ref/Length])[ker]+1.

(RefLink[ListConvolve, paclet:ref/ListConvolve])[ker,list] allows no overhangs and is equivalent to (RefLink[ListConvolve, paclet:ref/ListConvolve])[ker,list,{-1,1}].

(RefLink[ListConvolve, paclet:ref/ListConvolve])[ker,list,k] is equivalent to (RefLink[ListConvolve, paclet:ref/ListConvolve])[ker,list,{k,k}].

The values of (Subscript[k, L]) and (Subscript[k, R]) in (RefLink[ListConvolve, paclet:ref/ListConvolve])[ker,list,{(Subscript[k, L]),(Subscript[k, R])}] determine the amount of overhang to allow at each end of list.

Common settings for {(Subscript[k, L]),(Subscript[k, R])} are:

With maximal overhang at one end only, the result from (RefLink[ListConvolve, paclet:ref/ListConvolve]) is the same length as list.

(RefLink[ListConvolve, paclet:ref/ListConvolve])[ker,list,{(Subscript[k, L]),(Subscript[k, R])},padlist] effectively lays down repeated copies of padlist, then superimposes one copy of list on them and forms a convolution of the result.

Common settings for padlist are:

(RefLink[ListConvolve, paclet:ref/ListConvolve]) works with multidimensional kernels and lists of data.

(RefLink[ListConvolve, paclet:ref/ListConvolve])[ker,list,{{(Subscript[k, L1]),(Subscript[k, L2]),…},{(Subscript[k, R1]),(Subscript[k, R2]),…}}] forms the cyclic convolution whose {1,1,…} element contains ker[[(Subscript[k, L1]),(Subscript[k, L2]),…]]list[[1,1,…]], and whose {-1,-1,…} element contains ker[[(Subscript[k, R1]),(Subscript[k, R2]),…]]list[[-1,-1,…]].

{(Subscript[k, L]),(Subscript[k, R])} is taken to be equivalent to {{(Subscript[k, L]),(Subscript[k, L]),…},{(Subscript[k, R]),(Subscript[k, R]),…}}.

When a function h is specified to use in place of (RefLink[Plus, paclet:ref/Plus]), explicit nested h expressions are generated with a depth equal to the depth of ker.

(RefLink[ListConvolve, paclet:ref/ListConvolve]) works with exact numbers and symbolic data as well as approximate numbers.

OpenersPrimaryExamplesSection(Spacer1)Examples  (34)

OpenersExampleSection0(Spacer1)Basic Examples  (4)

Convolve a kernel {x,y} with a list of data:

ListConvolve[{x,y},{a,b,c,d,e,f}]

Make a cyclic convolution the same length as the original data:

ListConvolve[{x,y},{a,b,c,d,e,f},1]

Align element 2 in the kernel with successive elements in the data:

ListConvolve[{x,y},{a,b,c,d,e,f},2]

Pad with zzz instead of using the data cyclically:

ListConvolve[{x,y},{a,b,c,d,e,f},1,zzz]

Two-dimensional convolution:

ListConvolve[{{1,1},{1,1}},{{a,b,c},{d,e,f},{g,h,i}}]

OpenersExampleSection1(Spacer1)Scope  (9)

OpenersExampleSubsection0(Spacer1)Overhangs and Alignments  (4)

"Slide" the kernel along the data, allowing no overhangs:

ListConvolve[{x,y,z},{1,2,3,4,5,6}]

Maximal overhang at the beginning; none at the end:

ListConvolve[{x,y,z},{1,2,3,4,5,6},1]

Maximal overhang at the end; none at the beginning:

ListConvolve[{x,y,z},{1,2,3,4,5,6},-1]

Maximal overhangs at both beginning and end:

ListConvolve[{x,y,z},{1,2,3,4,5,6},{1,-1}]

Align element 1 of the kernel with the first element of the data:

ListConvolve[{x,y,z},{1,2,3,4,5,6},1]

Align element 2 of the kernel with the first element of the data:

ListConvolve[{x,y,z},{1,2,3,4,5,6},2]

Align element 3 of the kernel with the first element of the data:

ListConvolve[{x,y,z},{1,2,3,4,5,6},3]

Align the last element of the kernel with the first element of the data:

ListConvolve[{x,y,z},{1,2,3,4,5,6},-1]

Align the first element of the kernel with both the first and last elements of the data:

ListConvolve[{x,y,z},{1,2,3,4,5,6},{1,1}]

Align element 2 of the kernel with the first element of the data:

ListConvolve[{x,y,z},{1,2,3,4,5,6},{2,1}]

Align element 2 of the kernel with the last element of the data:

ListConvolve[{x,y,z},{1,2,3,4,5,6},{1,2}]

OpenersExampleSubsection1(Spacer1)Data Padding  (2)

Use padding aa:

ListConvolve[{x,y,z},{1,2,3,4,5},1,aa]

Cyclically use a list of padding elements:

ListConvolve[{x,y,z},{1,2,3,4,5},1,{aa,bb}]

ListConvolve[{x,y,z},{1,2,3,4,5},1,{aa,bb,cc}]

ListConvolve[{x,y,z},{1,2,3},{1,-1},{aa,bb,cc}]

OpenersExampleSubsection2(Spacer1)Higher Dimensions  (3)

Allow no overhangs:

ListConvolve[{{a,b},{c,d}},{{1,2,3},{4,5,6},{7,8,9}}]

Align with the {1,1} elements of the kernel and data:

ListConvolve[{{a,b},{c,d}},{{1,2,3},{4,5,6},{7,8,9}},1]

The result has the same dimensions as the input data:

Dimensions[%]

Give a different overhang in each dimension:

ListConvolve[{{a,b},{c,d}},{{1,2,3},{4,5,6},{7,8,9}},{{1,1},{2,2}}]

OpenersExampleSection2(Spacer1)Generalizations & Extensions  (4)

(RefLink[ListConvolve, paclet:ref/ListConvolve]) works with sparse arrays:

ListConvolve[{a,b,c},SparseArray[6->x,20]]

Use f in place of (RefLink[Times, paclet:ref/Times]):

ListConvolve[{x,y},{1,2,3,4},1,0,f]

Use g in place of (RefLink[Plus, paclet:ref/Plus]):

ListConvolve[{x,y},{1,2,3,4},1,0,f,g]

ListConvolve[{x,y},{1,2,3,4},1,0,f,List]

Use f and g in place of (RefLink[Times, paclet:ref/Times]) and (RefLink[Plus, paclet:ref/Plus]), with empty data padding:

ListConvolve[{x,y,z},{1,2,3},1,{},f,g]

ListConvolve[{x,y,z},{1,2,3},-1,{},f,g]

ListConvolve[{x,y,z},{1,2,3},{1,-1},{},f,g]

(RefLink[ListConvolve, paclet:ref/ListConvolve]) works with (RefLink[TimeSeries, paclet:ref/TimeSeries]):

ts=TimeSeries[Table[Subscript[x,t],{t,12}]]

ts["Path"]

ListConvolve[{1/2,1/2},ts,{1}]

%["Path"]

OpenersExampleSection3(Spacer1)Applications  (9)

Find a moving average:

ListConvolve[{1,1}/2,{a,b,c,d,e}]

Or use the (RefLink[MovingAverage, paclet:ref/MovingAverage]) function:

MovingAverage[{a,b,c,d,e},2]

Smooth noisy data:

data=Table[Sqrt[x]+RandomReal[],{x,30}];

ListLinePlot[data]

ListLinePlot[ListConvolve[{1,1,2,1,1}/6,data]]

Find the autocorrelation of a list:

data=Table[Mod[i^2,17],{i,100}];

ListLinePlot[ListConvolve[data,data,{1,1}]]

Apply a simple image processing filter:

ArrayPlot[CellularAutomaton[150,{{1},0},30]]

ArrayPlot[ListConvolve[{{-1,1},{1,-1}},CellularAutomaton[150,{{1},0},30]]]

Multiply polynomials by convolving coefficient lists:

CoefficientList[(a+b x+c x^2)(1+2x+3x^2+4x^3),x]

ListConvolve[{a,b,c},{1,2,3,4},{1,-1},0]

Multiply numbers by convolving digit lists:

ListConvolve[IntegerDigits[24561],IntegerDigits[1247],{1,-1},0]

FromDigits[%,10]

24561 1247

Pascal's triangle:

Column[NestList[ListConvolve[{1,1},#,{1,-1},0]&,{1},5],Center]

Additive cellular automaton in base 5:

ArrayPlot[NestList[Mod[ListConvolve[{2,3,1},#,2],5]&,SparseArray[50->1,101],50]]

Fast multiplication of high-degree polynomials:

p1[x_] = RandomInteger[9, 101].x^Range[0,100];
p2[x_] = RandomInteger[9, 101].x^Range[0,100];

Use (RefLink[ListConvolve, paclet:ref/ListConvolve]) with maximal overhangs and zero padding:

c3 = ListConvolve[CoefficientList[p1[x],x], CoefficientList[p2[x],x],{1,-1}, 0] ;

p3[x_] = c3.x^Range[0, Length[c3] - 1];

p3[x] == Expand[p1[x] p2[x]]

OpenersExampleSection4(Spacer1)Properties & Relations  (7)

Cyclic convolution is equivalent to multiplication in the discrete Fourier transform domain:

{a, b} = RandomReal[1, {2,31}];

ListConvolve[a, b, {1,1}] ==InverseFourier[Fourier[a] Fourier[b]] Sqrt[31]

Convolve with a single element:

ListConvolve[{1},{1,2,3,4,5,6}]

ListConvolve[{1},{1,2,3,4,5,6},2]

A kernel of the same length as the data, with no overhangs, is like a reversed dot product:

ListConvolve[{x,y,z},{a,b,c}]

Successive differences:

ListConvolve[{1,-1},{a,b,c,d,e}]

Differences[{a,b,c,d,e}]

Align with successive elements:

Table[ListConvolve[{x,y,z},{1,2,3,4,5,6},i],{i,3}]//Column

Table[ListConvolve[{x,y,z},{1,2,3,4,5,6},i],{i,-3,-1}]//Column

Varying alignments:

Table[ListConvolve[{1,1},{1,1,1,1},{i,j}],{i,4},{j,4}]//Grid

Grid[Table[ListConvolve[{1,1},{1,1,1,1},{i,-j}],{i,4},{j,4}]]

Grid[Table[ListConvolve[{1,1},{1,1,1,1},{-i,j}],{i,4},{j,4}]]

Varying alignments, with padding:

Table[ListConvolve[{1,1},{1,1,1,1},{i,j},0],{i,4},{j,4}]//Grid

Table[ListConvolve[{1,1},{1,1,1,1},{i,-j},0],{i,4},{j,4}]//Grid

Table[ListConvolve[{1,1},{1,1,1,1},{-i,j},0],{i,4},{j,4}]//Grid

OpenersExampleSection5(Spacer1)Possible Issues  (1)

By default, the output is not the same length as the input:

ListConvolve[{1,1},{1,2,3,4,5}]

Use overhangs to make the output the same length as the input:

ListConvolve[{1,1},{1,2,3,4,5},1]

Use overhangs to do the same in 2D:

ListConvolve[{{1,1},{1,1}},{{1,2,3},{4,5,6},{7,8,9}},1]

({{DocumentationFooterIconsRelatedFunction.png, ({{See Also}, {(RefLink[ListCorrelate, paclet:ref/ListCorrelate])  ▪  (RefLink[ListDeconvolve, paclet:ref/ListDeconvolve])  ▪  (RefLink[ImageConvolve, paclet:ref/ImageConvolve])  ▪  (RefLink[LinearRecurrence, paclet:ref/LinearRecurrence])  ▪  (RefLink[MovingAverage, paclet:ref/MovingAverage])  ▪  (RefLink[RecurrenceFilter, paclet:ref/RecurrenceFilter])  ▪  (RefLink[Partition, paclet:ref/Partition])  ▪  (RefLink[Accumulate, paclet:ref/Accumulate])  ▪  (RefLink[Differences, paclet:ref/Differences])  ▪  (RefLink[Inner, paclet:ref/Inner])  ▪  (RefLink[CellularAutomaton, paclet:ref/CellularAutomaton])  ▪  (RefLink[ArrayFilter, paclet:ref/ArrayFilter])  ▪  (RefLink[PadLeft, paclet:ref/PadLeft])  ▪  (RefLink[DiscreteConvolve, paclet:ref/DiscreteConvolve])  ▪  (RefLink[DiskMatrix, paclet:ref/DiskMatrix])  ▪  (RefLink[GaussianMatrix, paclet:ref/GaussianMatrix])}})}})

({{DocumentationFooterIconsRelatedTutorial.png, ({{Tutorials}, {▪(RefLinkPlain[Convolutions and Correlations, paclet:tutorial/ConvolutionsAndCorrelations])}})}})

({{DocumentationFooterIconsRelatedGuide.png, ({{Related Guides}, {▪(RefLinkPlain[Data Transforms and Smoothing, paclet:guide/DataTransformsAndSmoothing])}, {▪(RefLinkPlain[Signal Processing, paclet:guide/SignalProcessing])}, {▪(RefLinkPlain[Handling Arrays of Data, paclet:guide/HandlingArraysOfData])}, {▪(RefLinkPlain[Linear and Nonlinear Filters, paclet:guide/LinearAndNonlinearFilters])}, {▪(RefLinkPlain[Image Filtering & Neighborhood Processing, paclet:guide/ImageFilteringAndNeighborhoodProcessing])}, {▪(RefLinkPlain[Fourier Analysis, paclet:guide/FourierAnalysis])}, {▪(RefLinkPlain[Numerical Data, paclet:guide/NumericalData])}, {▪(RefLinkPlain[Scientific Data Analysis, paclet:guide/ScientificDataAnalysis])}, {▪(RefLinkPlain[Summation Transforms, paclet:guide/SummationTransforms])}})}})

({{(Spacer1), ({{(Spacer1)Related Links}, {(Spacer1)▪(RefLinkPlain[(Spacer1)Implementation notes: Numerical and Related Functions, paclet:tutorial/SomeNotesOnInternalImplementation#15670])}, {(WebLink[DocumentationFooterIconsRelatedLinks-NKS.png(Spacer1)NKS|Online, http://www.wolframscience.com/nksonline/index/search.cgi?SearchIndex=ListConvolve]) ((WebLink[A New Kind of Science, http://www.wolframscience.com/nksonline/]))}})}})