1D快速卷积没有FFT [英] 1D Fast Convolution without FFT

问题描述

我需要对2大阵列的1D回旋。我使用C＃的代码，但它需要一个loooong时间来运行。

I need an 1D Convolution against 2 big arrays. I'm using this code in C# but it takes a loooong time to run.

我知道，我知道！ FFT卷积是非常快的。但是，在这个项目中我不能使用它。
它是项目不使用FFT（请不要问为什么：/）的一个制约因素。

I know, i know! FFT convolutions is very fast. But in this project i CAN'T use it. It is a constraint of the project to not use FFT (please don't ask why :/).

这是我在C＃代码（从移植MATLAB，顺便说一句）：

This is my code in C# (ported from matlab, by the way):

var result = new double[input.Length + filter.Length - 1];
for (var i = 0; i < input.Length; i++)
{
    for (var j = 0; j < filter.Length; j++)
    {
        result[i + j] += input[i] * filter[j];
    }
}

所以，任何人都知道任何快速卷积算法WIDTHOUT FFT？

So, anyone knows any fast convolution algorithm widthout FFT?

推荐答案

卷积在数值上是一样的一个额外的环绕步多项式乘法。因此，所有的多项式和大整数乘法算法可以用来执行卷积。

Convolution is numerically the same as a polynomial multiplication with an extra wrap-around step. Therefore, all the polynomial and large integer multiplication algorithms can be used to perform convolution.

FFT是最快捷的O（N日志（N））的唯一途径-时间。但是你可以使用分而治之的仍然得到分二次运行时间接近如 Karatsuba算法。

FFT is the only way to get the fast O(n log(n)) run-time. But you can still get sub-quadratic run-time using the divide-and-conquer approaches like Karatsuba's algorithm.

Karatsuba算法是相当容易实现的，一旦你了解它是如何工作的。它运行在为O（n ^ 1.585），并很可能会比试图更快的超级优化经典为O（n ^ 2）的方法。

Karatsuba's algorithm is fairly easy to implement once you understand how it works. It runs in O(n^1.585), and will probably be faster than trying to super-optimize the classic O(n^2) approach.

这篇关于1D快速卷积没有FFT的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！