  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.
