ml-convolution

convolution

Convolution using the FFT or direct algorithm.

Installation

npm install ml-convolution

Usage

One execution

import { directConvolution, fftConvolution } from 'ml-convolution';

const input = [0, 1, 2, 3];
const kernel = [-1, 1, -1];

const outputDirect = directConvolution(input, kernel); // [-1, -1, -2, 1]
const outputFFT = fftConvolution(input, kernel); // [-1, -1, -2, 1]

The functions both take an optional third argument to determine the way borders are processed. The default value, CONSTANT, will consider that the values out of the bounds are all 0. If it is set to CUT, borders will be ignored and the result will be smaller than te input by kernel.length - 1:

const outputDirect = directConvolution(input, kernel, 'CUT'); // [-1, -2]

Optimized, multiple executions

If you need to execute the convolution many times with the same kernel and input length, you should consider instead to use the class-based API:

import { DirectConvolution, FFTConvolution } from 'ml-convolution';

// const input = [0, 255, 255, 255, 255, 0, 0, 0];
const kernel = [0.1, 0.2, 0.3];

// First parameter is the size of the inputs and allows to pre-allocate an array with the correct size
const direct = new DirectConvolution(8, kernel, 'CUT');

// The convolve function mutates the same array at each execution
direct.convolve([0, 255, 255, 255, 255, 0, 0, 0]); // [ 127.5, 153, 153, 76.5, 25.5, 0 ]
direct.convolve([255, 0, 0, 255, 255, 255, 0, 0]); // [ 25.5, 76.5, 127.5, 153, 76.5, 25.5 ]

const fft = new FFTConvolution(8, kernel, 'CONSTANT');
fft.convolve([0, 255, 255, 255, 255, 0, 0, 0]); // [ 76.5, 127.5, 153, 153, 76.5, 25.5, 0, 0 ]
fft.convolve([255, 0, 0, 255, 255, 255, 0, 0]); // [ 51, 25.5, 76.5, 127.5, 153, 76.5, 25.5, 0 ]

Benchmark

With small kernels, direct convolution is usually faster:
Current results suggest that from a kernel size around 64, FFT convolution should be used.

Data x Kernel	fft [ops/s]	direct [ops/s]
128 x 5	97889	569110
128 x 11	99403	280271
128 x 17	97686	181608
128 x 33	94633	93847
128 x 65	96585	49320
128 x 129	97189	25346
128 x 513	21771	6469
512 x 5	20712	144025
512 x 11	21134	73189
512 x 17	21201	44320
512 x 33	21037	23591
512 x 65	21398	12405
512 x 129	21514	6358
512 x 513	21494	1618
2048 x 5	4746	36360
2048 x 11	4740	18422
2048 x 17	4735	11248
2048 x 33	4689	5927
2048 x 65	4740	3100
2048 x 129	4741	1591
2048 x 513	4753	405
4096 x 5	2068	18201
4096 x 11	2062	9241
4096 x 17	2071	5629
4096 x 33	2069	2976
4096 x 65	2079	1551
4096 x 129	2074	797
4096 x 513	2079	203
16384 x 5	370	4036
16384 x 11	371	2295
16384 x 17	377	1390
16384 x 33	374	748
16384 x 65	370	389
16384 x 129	375	199
16384 x 513	376	51
65536 x 5	70	991
65536 x 11	70	541
65536 x 17	70	351
65536 x 33	69	186
65536 x 65	71	97
65536 x 129	71	50
65536 x 513	70	13
262144 x 5	10	247
262144 x 11	10	135
262144 x 17	10	88
262144 x 33	10	47
262144 x 65	10	24
262144 x 129	10	12
262144 x 513	10	3
1048576 x 5	2	60
1048576 x 11	2	32
1048576 x 17	2	22
1048576 x 33	2	12
1048576 x 65	2	6
1048576 x 129	2	3
1048576 x 513	2	1

License

MIT