# How to zero pad a 3d data and apply fast convolution?

I have two sequences,

• Let $$A$$ be the first sequence whose dimensions are $$(5, 5, 3)$$ takes complex values
• Let $$B$$ be the second sequence whose dimensions are $$(5, 5, 1)$$ also takes complex values

I would like to use $$\mathrm{fftw}$$ to perform fast convolution to get the output $$C$$. I presume the output dimension is also $$(5,5,3)$$? But I am confused.

My questions are,

1. Is output dimension correct? For $$\mathrm{1d}$$ the output length is $$M+N -1$$, presume the $$M$$ and $$N$$ are the lengths of some sequence $$R$$ and $$S$$. But I can't figure out for $$\mathrm{3d}$$ data.
2. How to zero-pad $$B$$, in-case zero padding is necessary? Is it like increasing the $$z$$ dimension to $$3$$ to make it $$(5, 5, 3)$$ for $$B$$ too?
• I see- here is your originating question. I think you need to specify if the result needs to be linear convolution or circular convolution (with linear convolution each dimension will then be N+M-1 long but you many also only be wanting the result where both completely overlap)—- I haven’t looked under the hood of FFTW but are you specifically wanting to use Bluestein’s algorithm as you desire the DFT result on each dimension or is it actually only fast convolution that you need? Commented Apr 5, 2022 at 12:03
• 1) There was one specific problem where a customer wanted the filter response in time-domain to measure filter length etc., (We have a commercial tool that gives filter response in frequency domain only) Commented Apr 5, 2022 at 15:10
• My boss took the Bluestein (inverse of it) to get the time response. I was curious about the kernel etc., Commented Apr 5, 2022 at 15:14
• 2) Personally implemented FMM (Fast Multipole Method) for Electric Field Integral Equation and there is this convolution problem. Commented Apr 5, 2022 at 15:16
• 3) I am not into signal processing but I have learned a bit now. Nevertheless I don't really know when to use linear or circular convolution. Commented Apr 5, 2022 at 15:19

1. Length of outputs after the convolution are per dimension so $$L_d=M_d+N_d-1$$ where $$d$$ is an index over the dimension, $$L_d$$ is the length of the output in the dth dimension, $$M_d$$ is the length of the first input in the dth dimension, and $$N_d$$ is the length of the second input in the dth dimension. So for your example: (5, 5, 3) & (5, 5, 1) -> (9, 9, 3).
• I presume you meant $L_d=M_d + N_d -1$ instead of $L_d = M_d + N + d - 1$ Commented Mar 24, 2022 at 9:37