0
$\begingroup$

Let $A,B\in \mathbb{R}^{d\times d\times d}$. The 3D circular convolution $\text{conv}(A,B)$ can then be computed as $F^{-1}(F(A)\odot F(B))$ where $F(\cdot)$ denotes the 3D discrete Fourier transform and $\odot$ denotes entry-wise multiplication. By using the fast Fourier transform I can then compute $\text{conv}(A,B)$ in $O(d^3\lg d)$ time.

I only need $d^2$ entries of $\text{conv}(A,B)$ and $A,B$ only contain $d^2$ non-zero entries. Is it possible to compute $d^2$ entries of $\text{conv}(A,B)$ faster than $O(d^3)$?

Specifically, $A_{i,j,k}=0$ for all $i\neq 0$ and $B_{i,j,k}=0$ for all $j\neq 0$, and I want the $d^2$ entires $\text{conv}(A,B)_{i,k,d-1}$ for $i,k=0,...,d-1$ .

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Have you attempted the 2D version of this problem, specifically A,B in $\mathbb{R}^{d \times d}$ and A, B contain only $d$ non zero entries? $\endgroup$ – Dsp guy sam Apr 27 '20 at 9:38
  • $\begingroup$ The 1d variant where $A_{ij}=0$ for all $i\neq 0$ and $B_{ij}=0$ for all $j\neq 0$ each entry of the convolution can be computed by just one multiplication, i.e., in $O(1)$ time. This means I can compute $d$ entries in $O(d)$ time. I can't get this to extend nicely to 3D. In 3D, each entry of the convolution can be computed by $d$ multiplications. Since there are $d^2$ entries this gives $O(d^3)$, and I want less than $O(d^3)$. $\endgroup$ – Alexander Mathiasen Apr 28 '20 at 12:32
  • $\begingroup$ No. You have two free variables that give you $d^2$ complexity. The remaining variable needs to be in a convolution product, giving you another $d \log d$ term. So without additional information, you cannot improve the complexity. But that does not mean you cannot reduce the execution time by a constant factor by rewriting the problem. $\endgroup$ – Jazzmaniac Apr 28 '20 at 13:11
  • $\begingroup$ I agree that one needs to read $A$ and $B$ and this gives a lower bound of $d^2$ time. I do not understand what you mean by "remaining variable"? Also, do you claim that it is impossible to compute any $d^2$ entries of $\text{conv}(A,B)$ in less than $O(d^3\lg d)$? Because that statement is false, I have an algorithm that computes $\text{conv}(A,B)_{i,d-1,k}$ for $i,k=0,...,d-1$ in $O(d^2 \lg d)$ time (notice the difference between $_{i,d-1,k}$ and $_{i,k,d-1}$). $\endgroup$ – Alexander Mathiasen Apr 29 '20 at 15:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.