LolNewacc's blog

Need help with FFT.
By LolNewacc, history, 2 years ago, translation, In English

There is a well-known algorithm which uses padding to the nearest power of two, so dft could be found by standart D&C technique. I have a problem which requires solving linear equation with circulant matrix. There is a formula, which I need to use at a certain step

$$$x=IFFT(\frac{FFT(c)}{FFT(b)})$$$

And I need here to find FFT of both vectors without padding. I don't really understand how should i do it without really struggling (like D&C and strangely divide vectors then multiply not by -1 but by some power of root of unity and then do some random stuff). There is a built-in function in pandas(actually there is even solve_circulant function in scipy), but i can't use them (because cf doesn't provide numpy :) ). Is there a relatively easy way to calculate it(mb using result with padding) or maybe there is a source(python/C++) which i could just copy for my purposes?

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
2 years ago, # |
  Vote: I like it +13 Vote: I do not like it

I had the same issue when i was doing the recent Div 3, E. But i did not find a way of solving it.

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yeah, i want to solve generalization of this problem(i guess it's quite an overkill for problem itself)

    → Reply