计算科学 - 快速（更）计算两个卷积的点积？ - 吾爱随笔录

让 $a,b,c,d\in\mathbb{R}^n$ . 是否可以计算

⟨ a * b, c * d ⟩

$\langle a*b,c*d\rangle$ 快于 6 个 FFT？

我可以通过进行正常卷积来使用 6 个 FFT，每个卷积 3 个 FFT。

在我的应用程序中，我知道 $b, d$ 前期并且可以做预处理，所以成本实际上是4个FFT。我能做得比这更好吗？

我认为这可能是可能的原因是因为 FFT 是单一的，所以也许有一种方法可以在卷积中省略逆 FFT。

[编辑] 其中卷积定义为：

(a * b)_{i} = \sum_{j = 1}^{i} a_{j} b_{n + j - i}

$(a*b)_i=\sum_{j=1}^i a_jb_{n+j-i}$