# Breaking a convolution into smaller pieces

For a project I need to do convolution and i use gpu for calculations. Sometimes I have to deal with kernel sizes of 50x50 and this size of kernel is sufficiently large that it chokes the gpu. (not enough memory svailable by the gpu) I need to find a way to break the kernel into smaller sizes (8x8 or similar) and do the convolution this way (i.e. piece by piece and later stitch together) so that I can realize gpu enhancements. What is the best way to break these kernels into smaller pieces? (I have no prior knowledge of kernel size so the solution must be something I can deal with in run time. )

-
It's not clear from your description what the bottleneck of your application is, so you may not get very specific answers. If you can share more details, that may help. –  Jason R Dec 18 '12 at 16:37
@JasonR the bottleneck is the kernel size. The internal scratch memory of the gou cannot deal with large kernels. I need to break this operation 10x10 type kernels and run. I just don't know how to break the kernels. –  Ktuncer Dec 19 '12 at 0:06
This link blogs.msdn.com/b/nativeconcurrency/archive/2011/11/01/… might help –  Naresh Dec 19 '12 at 4:18

Yes, you can split them up. Convolution is a linear process, which means that superposition holds. Thus, you can break up any convolution kernel $k$ into multiple parts ($k_1, k_2, ... k_N$) such that $k = \sum k_i$.

For example, if you had a convolution kernel that looked like [1 2 3 4] (granted this is a silly kernel, but does fine for purposes of illustration), you could break it up into the following kernels, [1 2 0 0] and [0 0 3 4]. Now, you could simply do the convolutions like normal and then add the results together. The sum would be equal to the convolution product of the original kernel.

Doing that would be inefficient, though, both in terms of computations and memory. Instead, you could simply drop the 0's at the ends of the "sub-kernels", and do the convolutions using [1 2] and [3 4]. The one tricky part to this is that you have to offset the results before adding them together to get the correct answer.

-
+1 , very nice. Though you will need twice the amount of memory (at least) for this method. –  Andrey Dec 20 '12 at 0:43
Fantastic thanks. –  Ktuncer Dec 20 '12 at 0:47

The convolution operation is associative.

$(S ** g) ** h = S ** ( g ** h )$

This means that if you find two kernels $g,h$ such that $g**h = k$, (where $k$ is your kernel), you can split your kernel into several parts, and apply each one individually. Each of the kernels can be smaller in size. The most known example of such kernels are Gaussian kernels.

Sometimes, it is even possible to split the kernel into two parts, such that each works only on one dimension. This quality is also possessed by Gaussian kernels.

To sum up, check if your kernel can be represented as convolution of two smaller kernels. This can be found out by checking the rank of the matrix. If it is equal to 1, it is separable. (That is because all of the rows are linear combinations of the first row).

-
I don't know the kernel until run time. What is the best way to separate kernels? Or is there an operation to find out if the kernel is separable ? –  Ktuncer Dec 19 '12 at 16:26
@Ktuncer, please see edit –  Andrey Dec 19 '12 at 17:28