The convolution of two vectors, `u`

and `v`

,
represents the area of overlap under the points as `v`

slides
across `u`

. Algebraically, convolution is the same
operation as multiplying polynomials whose coefficients are the elements
of `u`

and `v`

.

Let `m = length(u)`

and `n = length(v)`

.
Then `w`

is the vector of length `m+n-1`

whose `k`

th
element is

The sum is over all the values of `j`

that
lead to legal subscripts for `u(j)`

and `v(k-j+1)`

,
specifically `j`

`=`

`max(1,k+1-n):1:min(k,m)`

.
When `m`

`=`

`n`

,
this gives

w(1) = u(1)*v(1)
w(2) = u(1)*v(2)+u(2)*v(1)
w(3) = u(1)*v(3)+u(2)*v(2)+u(3)*v(1)
...
w(n) = u(1)*v(n)+u(2)*v(n-1)+ ... +u(n)*v(1)
...
w(2*n-1) = u(n)*v(n)