An accurate O(N ²) floating point algorithm for the Crum transform of the KdV equation

Abstract

We present an algorithm to compute the N-fold Crum transform (also known as the dressing method) for the Korteweg–de Vries equation (KdV) accurately in floating point arithmetic. This transform can be used to generate solutions of the KdV equation, e.g. as a part of the inverse Non-linear Fourier Transform. Crum transform algorithms that sequentially add the N eigenvalues to the solution with a chain of N Darboux transforms have a computational complexity of O(N
²), but suffer inevitably from singular intermediate results during the computation of certain regular Crum transforms. Algorithms that add all N eigenvalues at once do not have that flaw, but have a complexity of O(N
³) and are often even less accurate for other reasons. Our algorithm has a complexity of O(N
²). It makes use of a chain of 2-fold Crum transforms and, if N is odd, one Darboux transform. Hence, our algorithm adds two eigenvalues at a time instead of one whenever possible. We prove that with the right eigenvalue ordering, this avoids artificial singularities for all regular Crum transforms. Furthermore, we demonstrate that our algorithm is considerably more accurate in floating point arithmetic than benchmark algorithms found in the literature. At the same error tolerance, N can be three to seven times as high when using our algorithm instead of the best among the benchmark algorithms.