9

Anybody know about the fastest method for calculating convolution? Unfortunately the matrix which I deal with is very large (500x500x200) and if I use convn in MATLAB it takes a long time (I have to iterate this calculation in a nested loop). So, I used convolution with FFT and it is faster now. But, I am still looking for a faster method. Any idea?

4

3 回答 3

16

如果您的内核是可分离的，则通过执行多个连续的 1D 卷积将实现最大的速度增益。

MathWorks 的 Steve Eddins 在他的博客上描述了当内核在 MATLAB 上下文中可分离时如何利用卷积的关联性来加速卷积。对于P-by-Q内核，执行两个单独的顺序卷积与 2D 卷积相比的计算优势是PQ/(P+Q)，这对应于 9x9 内核的 4.5x 和 15x15 内核的 ~11x。编辑：在这个问答中给出了一个有趣的不知情的证明。

为了弄清楚内核是否可分离（即两个向量的外积），博客继续描述如何检查您的内核是否可与 SVD 分离以及如何获得一维内核。他们的示例是针对 2D 内核的。有关 N 维可分离卷积的解决方案，请查看此 FEX 提交。

另一个值得指出的资源是英特尔的 3D 卷积 SIMD (SSE3/SSE4) 实现，其中包括源代码和演示文稿。该代码适用于 16 位整数。除非您转向 GPU（例如cuFFT），否则可能很难比 Intel 的实现更快，后者还包括Intel MKL。在 MKL 文档的此页面底部有一个 3D 卷积（单精度浮点）示例（链接已修复，现在反映在https://stackoverflow.com/a/27074295/2778484中）。

于 2013-12-12T23:01:03.013 回答
2

您可以尝试重叠添加和重叠保存方法。它们涉及将您的输入信号分解成更小的块，然后使用上述任何一种方法。

FFT 最有可能——我可能错了——最快的方法，特别是如果您使用 MATLAB 中的内置例程或 C++ 中的库。除此之外，将输入信号分成更小的块应该是一个不错的选择。

于 2013-12-12T21:34:58.150 回答
1

我有 2 种方法来计算 fastconv

和 2 好于 1

1-犰狳，您可以使用犰狳库使用此代码计算转换

cx_vec signal(1024,fill::randn);
cx_vec code(300,fill::randn);
cx_vec ans = conv(signal,code);

2-使用 fftw ans sigpack 和 armadillo 库以这种方式计算快速转换，您必须在构造函数中初始化代码的 fft

FastConvolution::FastConvolution(cx_vec inpCode)
{
    filterCode = inpCode;
    fft_w = NULL;
}


cx_vec FastConvolution::filter(cx_vec inpData)
{
int length = inpData.size()+filterCode.size();
    if((length & (length - 1)) == 0)
    {

    }
    else
    {
        length = pow(2 , (int)log2(length) + 1);
    }
    if(length != fftCode.size())
        initCode(length);

    static cx_vec zeroPadedData;
    if(length!= zeroPadedData.size())
    {
        zeroPadedData.resize(length);
    }
    zeroPadedData.fill(0);
    zeroPadedData.subvec(0,inpData.size()-1) = inpData;


    cx_vec fftSignal = fft_w->fft_cx(zeroPadedData);
    cx_vec mullAns = fftSignal % fftCode;
    cx_vec ans = fft_w->ifft_cx(mullAns);
    return ans.subvec(filterCode.size(),inpData.size()+filterCode.size()-1);
}

void FastConvolution::initCode(int length)
{
    if(fft_w != NULL)
    {
        delete fft_w;
    }
    fft_w = new sp::FFTW(length,FFTW_ESTIMATE);
    cx_vec conjCode(length,fill::zeros);
    fftCode.resize(length);
    for(int i = 0; i < filterCode.size();i++)
    {
        conjCode.at(i) = filterCode.at(filterCode.size() - i - 1);
    }
    conjCode = conj(conjCode);
    fftCode = fft_w->fft_cx(conjCode);
}
于 2017-10-18T06:38:06.763 回答