Efficient Nonlinear Fourier Transform Algorithms of Order Four on Equispaced Grid
It provides more efficient algorithms for computing nonlinear Fourier transforms, which are important in signal processing and communications.
This paper develops nonlinear Fourier transform algorithms of order four on equispaced grids, achieving O(N log^2 N) complexity with superior accuracy-complexity trade-off compared to existing fast methods.
We explore two classes of exponential integrators in this letter to design nonlinear Fourier transform (NFT) algorithms with a desired accuracy-complexity trade-off and a convergence order of $4$ on an equispaced grid. The integrating factor based method in the class of Runge-Kutta methods yield algorithms with complexity $O(N\log^2N)$ (where $N$ is the number of samples of the signal) which have superior accuracy-complexity trade-off than any of the fast methods known currently. The integrators based on Magnus series expansion, namely, standard and commutator-free Magnus methods yield algorithms of complexity $O(N^2)$ that have superior error behavior even for moderately small step-sizes and higher signal strengths.