LolNewacc's blog

By LolNewacc, history, 3 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?

Full text and comments »

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