Adaptive Integral Method and Other FFT-Based Fast Algorithms

CG-FFT method proposed by Bojarski in 1971 was historically the very first known fast algorithm to reduce computational complexity and memory of MoM dense matrix equation solution from O(N²) to O(N log N). It did not receive much attention till 90s when adaptations of the algorithm to handling MoM solutions on unstructured meshes known as Adaptive Integral Method and Pre-Corrected FFT algorithms were proposed. Since then various popular fast solvers based on FFT acceleration scheme were developed including FastImp, FastCap, etc. In this talk we explain key stages of the FFT-based algorithms, various applications they are most suited for, as well as their advantages and disadvantages compared to other classes of fast algorithms such as Fast Multipole Method, Tensor Train Decomposition method and others.