0
$\begingroup$

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?
Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ 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? $\endgroup$
    – Dan Boschen
    Apr 5, 2022 at 12:03
  • $\begingroup$ 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) $\endgroup$
    – jomegaA
    Apr 5, 2022 at 15:10
  • $\begingroup$ My boss took the Bluestein (inverse of it) to get the time response. I was curious about the kernel etc., $\endgroup$
    – jomegaA
    Apr 5, 2022 at 15:14
  • $\begingroup$ 2) Personally implemented FMM (Fast Multipole Method) for Electric Field Integral Equation and there is this convolution problem. $\endgroup$
    – jomegaA
    Apr 5, 2022 at 15:16
  • $\begingroup$ 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. $\endgroup$
    – jomegaA
    Apr 5, 2022 at 15:19

1 Answer 1

Reset to default
2
$\begingroup$

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

  2. I'm not knowledgable on the function of FFTW, but may FFT implementations let you zero pad implicitly rather than explicitly. If you need to zero pad explicitly you'll want to have the input dimensions of each data set at a minimum the same size as the output after convolution to avoid the transients mixing (circular vs. linear convolution issue). Often the data structures are zero padded to a power of 2 as that is frequently the most efficient size for the FFT library (I don't know if that applies to FFTW). If you zero pad more than is needed you would then need to discard the excess after the IFFT.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I presume you meant $L_d=M_d + N_d -1$ instead of $L_d = M_d + N + d - 1$ $\endgroup$
    – jomegaA
    Mar 24, 2022 at 9:37
  • 1
    $\begingroup$ @jomegaA yes, thank you, I've edited to fix $\endgroup$
    – GrapefruitIsAwesome
    Mar 24, 2022 at 9:45
  • $\begingroup$ I would say I understood only the half. Any practical example will be helpful. Also I expect any symmetry in the output, that I must discard. $\endgroup$
    – jomegaA
    Mar 24, 2022 at 10:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.