Need help with FFT.

Revision en1, by LolNewacc, 2021-12-16 08:44:19

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?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English LolNewacc 2021-12-16 08:44:19 901 Initial revision for English translation
ru1 Russian LolNewacc 2021-12-16 08:39:31 901 Первая редакция (опубликовано)