# Compute $d^2$ entries of a 3D convolution faster than $O(d^3)$

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$$ .

• 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? – Dsp guy sam Apr 27 '20 at 9:38
• 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)$. – Alexander Mathiasen Apr 28 '20 at 12:32
• 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. – Jazzmaniac Apr 28 '20 at 13:11
• 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}$). – Alexander Mathiasen Apr 29 '20 at 15:13