Numerical Methods for Fast Nonlinear Fourier Transformation, Part I: Exponential Runge-Kutta and Linear Multistep Methods
For researchers in signal processing and nonlinear Fourier transforms, this work provides a theoretical foundation for fast numerical methods, but it is incremental as it extends existing exponential integrator theory to this specific application.
This paper analyzes exponential Runge-Kutta and linear multistep methods for nonlinear Fourier transformation, showing that both achieve O(N log^2 N) complexity and O(N^{-p}) convergence, with RK methods supporting both vanishing and periodic boundary conditions while LM methods only handle vanishing conditions.
The main objective of this series of papers is to explore the entire landscape of numerical methods for fast nonlinear Fourier transformation (NFT) within the class of integrators known as the exponential integrators. In this paper, we explore the theoretical aspects of exponential Runge-Kutta (RK) and linear multistep (LM) methods, in particular, the stability and convergence of these methods via the transfer matrix formulation. The analysis carried out in the paper shows that while the exponential LM methods are naturally amenable to FFT-based fast polynomial arithmetic, the RK methods require equispaced nodes to achieve that. Therefore, each these family of methods is capable of yielding a family of fast NFT algorithms such that the scattering coefficients can be computed with a complexity of $\mathscr{O}(N\log^2N)$ and a rate of convergence given by $\mathscr{O}(N^{-p})$ where $N$ is the number of samples of the signal and $p$ is order of the underlying discretization scheme. Further, while RK methods can accommodate vanishing as well as periodic boundary conditions, the LM methods can only handle the former type of boundary conditions without requiring a starting procedure. The ideas presented in this paper extend naturally to the family of integrators known as general linear methods which will be explored in a forthcoming paper.