fastnft / fnft

Fast numerical computation of (inverse) nonlinear Fourier transforms

FNFT: Fast Nonlinear Fourier Transforms

FNFT is a software library for the numerical computation of (inverse) nonlinear Fourier transforms, which are also known as (inverse) scattering transforms. The focus of the library is on fast algorithms, but it also contains non-fast methods. FNFT is written in C and comes with a MATLAB interface. A Python interface is available separately.

Currently Implemented Cases

Forward Transforms

• Nonlinear Schroedinger equation

  • Vanishing boundary conditions

    • Reflection coefficient and/or scattering coefficients (a and b)
    • Bound states (eigenvalues)
    • Norming constants and/or residues

  • (Quasi-)Periodic boundary conditions

    • Main spectrum
    • Auxiliary spectrum

• Korteweg-de Vries equation

  • Vanishing boundary conditions
    • Reflection coefficient and/or scattering coefficients (a and b)
    • Bound states (eigenvalues)
    • Norming constants and/or residues

• Manakov equation

  • Vanishing boundary conditions
    • Reflection coefficient and/or scattering coefficients (a, b1 and b2)
    • Bound states (eigenvalues)

Inverse Transforms

• Nonlinear Schroedinger equation

  • Vanishing boundary conditions
    • Inversion of reflection coefficients, b-scattering coefficients or the inverse Fourier transform of the b-coefficient
    • Bound states (eigenvalues) can be added with arbitrary norming constants/residuals

Mailing List

Please join the FNFT mailing list if you want to be notified about new releases of FNFT. You can subscribe either using the web interface, or by sending an email with the subject "subscribe" to [email protected].

Citation

If you use FNFT for your academic work, please cite the accompanying software paper. Latex users can use the following BibTex entry.

@article{FNFT2018,
    author  = {S. Wahls and S. Chimmalgi and P.J. Prins},
    title   = {{FNFT: A Software Library for Computing Nonlinear Fourier Transforms}},
    journal = {{The Journal of Open Source Software}},
    year    = {2018},
    volume  = {3},
    issue   = {23},
    pages   = {597},
    doi     = {10.21105/joss.00597},
    url     = {https://doi.org/10.21105/joss.00597},
    issn    = {2475-9066}
}

Installation

Please follow the instructions in the file INSTALL.md.

Getting started

Please read the file Getting-Started.md.

Community Guidelines

Please use the issue tracker to report any problems with the software. If you want to contribute to the development of FNFT, please email Sander Wahls.

Contributors

• Sander Wahls, KIT (since July 2023) and TU Delft (before)
• Shrinivas Chimmalgi, TU Delft
• Peter J. Prins, TU Delft
• Marius Brehler, TU Dortmund
• Lianne de Vries, student TU Delft

License

FNFT is provided under the terms of the GNU General Public License, version 2.

Acknowledgements

• This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 716669).

• FNFT incorporates code from the Fortran library eiscor.

• FNFT incorporates code from the C library Kiss FFT.

References

The algorithms in FNFT utilize ideas from the following references. More information can be found in the documentation of the individual routines.

• S. Wahls and H. V. Poor, "Introducing the fast nonlinear Fourier transform", Proc. IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP), Vancouver, Canada, May 2013.
• S. Wahls and H. V. Poor, "Fast Numerical Nonlinear Fourier Transforms", IEEE Transactions on Information Theory, vol. 61, no. 12, pp. 6957-6974, Dec. 2015.
• P. J. Prins and S. Wahls, "Higher order exponential splittings for the fast non-linear Fourier transform of the Korteweg-de Vries equation", Proc. 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). Piscataway, NJ, USA: IEEE. 2018. pp. 4524-4528.
• G. Boffetta and A. R. Osborne, "Computation of the direct scattering transform for the nonlinear Schroedinger equation", Journal of Computational Physics, vol. 102, no. 2, pp. 252-264, Oct. 1992.
• V. Aref, "Control and Detection of Discrete Spectral Amplitudes in Nonlinear Fourier Spectrum", Preprint, arXiv:1605.06328v1, May 2016.
• S. Hari and F. R. Kschischang, "Bi-Directional Algorithm for Computing Discrete Spectral Amplitudes in the NFT", Journal of Lightwave Technology, vol. 34, no. 15, pp. 3529-3537, Aug. 2016.
• J. L. Aurentz, T. Mach, L. Robol, R. Vandebril and D. S. Watkins, "Fast and backward stable computation of roots of polynomials, Part IIa: general backward error analysis", Technical Report no. TW 683, KU Leuven, Oct. 2017.
• V. Aref, S. T. Le and H. Buelow, "Modulation over Nonlinear Fourier Spectrum: Continuous and Discrete Spectrum", Journal of Lightwave Technology, vol. 36, no. 6, pp. 1289--1295, Mar. 2018.
• W. K. McClary, "Fast seismic inversion", Geophysics, vol. 48, no. 10, pp. 1371--1372, Oct. 1983.
• S. Wahls and H. V. Poor, "Fast Inverse Nonlinear Fourier Transform For Generating Multi-Solitons In Optical Fiber", Proc. IEEE International Symposium on Information Theory (ISIT’15), pp. 1676–1680, Hong Kong, China, Jun. 2015.
• S. Wahls and V. Vaibhav, "Fast Inverse Nonlinear Fourier Transforms for Continuous Spectra of Zakharov-Shabat Type", Withdrawn Preprint, Dec. 2016. arXiv:1607.01305v2 [cs.IT]
• S. Wahls, "Generation of Time-Limited Signals in the Nonlinear Fourier Domain via b-Modulation", Proc. European Conference on Optical Communcation (ECOC), Gothenburg, Sweden, Sep. 2017.
• J. Skaar, L. Wang and T. Erdogan, "On the synthesis of fiber Bragg gratings by layer peeling", IEEE Journal of Quantum Electronics, vol. 37, no. 2, pp. 165--173, Feb. 2001.
• S. Chimmalgi, P. J. Prins and S. Wahls, "Fast Nonlinear Fourier Transform Algorithms Using Higher Order Exponential Integrators", IEEE Access, vol. 7, pp. 145161--145176, Oct. 2019.
• P. J. Prins and S. Wahls, "Soliton Phase Shift Calculation for the Korteweg–De Vries Equation", IEEE Access, vol. 7, pp. 122914--122930, July 2019.
• S. Medvedev, I. Vaseva, I. Chekhovskoy and M. Fedoruk, "Exponential fourth order schemes for direct Zakharov-Shabat problem", Optics Express, vol. 28, pp. 20--39, 2020.
• J. Mertsching, "Quasiperiodie Solutions of the Nonlinear Schroedinger Equation", Fortschritte der Physik, vol. 35, pp. 519--536, 1987.
• L. de Vries, "Fast Numerical Nonlinear Fourier Transform Algorithms for the Manakov Equation", Master thesis, TU Delft, 2021.

fnft's Issues

Single and quad precision

Make changing FNFT_REAL to single and quad precision types work. Update tests where necessary.

CMake Error: CMAKE_C_COMPILER not set, after EnableLanguage

Hi, I'm trying to follow the INSTAL.md file on my windows 10 PC and get fail on the cmake step.

• installed scoop
• installed git (already had)
• installed cmake using scoop
• installed gcc using scoop (had issue at first since their servers are down, followed this issue: #68
• cloned the project
• created build dir, entered it
• running cmake .. -G"MinGW Makefiles" resulted the following error:

C:\FNFT\build>cmake .. -G"MinGW Makefiles"
-- The C compiler identification is GNU 9.3.0
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Check for working C compiler: C:/Users/yarde/scoop/apps/gcc/current/bin/gcc.exe - skipped
-- Detecting C compile features
-- Detecting C compile features - done
-- Looking for include file complex.h
CMake Error: CMAKE_C_COMPILER not set, after EnableLanguage
CMake Error at C:/Users/yarde/scoop/apps/cmake/3.21.1/share/cmake-3.21/Modules/CheckIncludeFiles.cmake:138 (try_compile):
  Failed to configure test project build system.
Call Stack (most recent call first):
  CMakeLists.txt:42 (check_include_files)


-- Configuring incomplete, errors occurred!
See also "C:/FNFT/build/CMakeFiles/CMakeOutput.log".

I'm pretty sure it has something to do with the gcc, not sure how to solve it, tried to install gcc using alternative method, same results..

Use the Interleaved Complex API introduced in Matlab R2018a if available

This would make calling mex files more efficient as the conversion to the complex array layout where real and imaginary parts are separated could be skipped.

https://nl.mathworks.com/help/matlab/matlab_external/matlab-support-for-interleaved-complex.html
https://nl.mathworks.com/help/matlab/matlab_external/upgrade-mex-files-to-use-interleaved-complex.html

Arbitrary numbers of samples

Remove the restriction that the number of samples has to be a power of two.

Common AKNS fscatter function

Create a common file for fscatter (akns_fscatter) as they utilize the same splitting schemes. kdv_fscatter and nse_fscatter should call akns_fscatter.

suggested update on the Installation guide for Scoop@Windows

in the the 3-step installation via scoop

scoop install git
scoop install cmake
scoop install gcc

scoop install gcc can install gcc now but is neither sufficient nor safe.

Due to the msys2's changes in compression method, Scoop had long been failed to install gcc (msys2's mingw build by default). As a breaking change, the recent version of Scoop has migrated to the WinLib's build of gcc for easier maintenance.

To stay with mingw64 toolchain without leaving CLI, here are working steps without Scoop's bucket hack:

launch PowerShell/CMD, then

# same
scoop install git
scoop install cmake

# change gcc to mingw
scoop install mingw

now everything should be ready to build FNFT. If Matlab is installed, you should see Matlab is found log during cmake, and *.mex files should be present in the build folder after successful building.

Windows 11 Install

Hello,

I installed FNFT on Windows 11.

I get these errors while testing
233 - fnft_nsev_inverse_test_truncated_soliton_2split2_modal (Exit code 0xc0000139
)
234 - fnft_version_test (Exit code 0xc0000139
)
Errors while running CTest
Output from these tests are in: C:/Users/andre/FNFT/build/Testing/Temporary/LastTest.log
Use "--rerun-failed --output-on-failure" to re-run the failed cases verbosely.
mingw32-make: *** [Makefile:70: test] Error 8

Moreover, I find two Matlab folders one with capital m one with small m. I copied all files libmex... mex... in both folders and the examples fail

Invalid MEX-file '~\FNFT\build\mex_fnft_kdvv.mexw64': Impossibile trovare la procedura specificata.

I remember I managed to install FNFT on a different PC in 2022 with Windows 10 and worked perfectly.

Thank you for your help.

Best regards,

Andrea

fnft__akns_fscatter_test_2split6A fails in development

Tested with gcc 6.4.0 and Gentoo Linux. The test fails on development (commit 79388e1).

14: Test command: /home/brehler/Development/FNFT/test/fnft__akns_fscatter/fnft__akns_fscatter_test_2split6A
14: Test timeout computed to be: 9.99988e+06
14: FNFT Error: Test failed.
14:  in akns_fscatter_test_2split6A(129)-0.1.1-dev
1/1 Test #14: fnft__akns_fscatter_test_2split6A ...***Failed    0.00 sec

0% tests passed, 1 tests failed out of 1

Total Test time (real) =   0.00 sec

The following tests FAILED:
         14 - fnft__akns_fscatter_test_2split6A (Failed)

bug in example / fnft_kdvv_example.c

In: 0.5 release / master branch
when compiled, the kdvv c-example (examples/fnft_kdvv_example.c) fails:

FNFT Error: Invalid argument opts->grid_spacing.
 in kdvv_compute_boundstates(593)-0.5.0
FNFT Error: Subroutine failure.
 in fnft_kdvv_base(480)-0.5.0
FNFT Error: Subroutine failure.
 in fnft_kdvv(242)-0.5.0
An error occured!

I suppose this is due to using the default grid-spacing of 0.0.
The example works fine if the grid spacing is explicitly defined, e.g. as

fnft_kdvv_opts_t opts = fnft_kdvv_default_opts();
// define grid spacing 
opts.grid_spacing = 0.001;

Best, Christoph

`akns_scatter.c` and `akns_discretization.c`contain PDE-specific lines of code

• Unless there is a very good reason too keep it, I would propose to revert commit d67c4f5 in which code specific to the KdV is added to akns_scatter.

That commit makes the behaviour of akns_scatter the same regardless of the PDE. It's semantically correct for NSE as well. It just happens to be a similarity transformation by identity in that case, so that you would be able to cut a corner as long as the code were only for NSE and not for AKNS in general. Without this addition the name should be something like akns_change_of_state to describe adequately what it returns.

Ah, I see. That actually depends on what you expect akns_scatter to do: Solve the AKNS scattering problem or return a scattering matrix of the form [a b' ; b a']. I expect it to do the former, even though with KdV in mind that indeed is inconsistent with the current documentation (which thus should be updated). However, it is consistent with what akns_fscatter actually returns.

The advantage of this approach is that you only have to understand the AKNS system to maintain this function. With the changes, you would also need to understand things specific to KdV to maintain this function. It would reduce the modularity of the code.

Indeed, you could avoid that call by changing akns_scatter_matrix() to akns_change_of_state_matrix(), but then you still need exactly the same calls in akns_scatter_bound_states() since the 1,1-entry of the change of state matrix in the basis you use must be 0 at an eigenvalue in order to use the bidirectional algorithm. That would create an inconsistency within the same file. Furthermore, the KdV and NSE specific transformation matrices need to stay in fnft__akns_discretization.c since only the akns_discretization is available in akns_scatter_bound_states(), so removing it from akns_scatter_matrix() doesn't solve your conceptual point.
All that a maintainer of that file should know is that in general a similarity transformation is needed to find the solution of the AKNS scattering problem, since the assumption just above eq. (3.1) in the AKNS paper does not always hold. That can be clarified with a few extra comments.

What akns_fscatter returns remains different either way. To make it consistent, the polynomials would have to be evaluated in akns_fscatter before return. However, that is not being done for NSE specific reasons, namely because nsev.c needs the polynomials for finding the eigenvalues.

Originally posted by @PJ-Prins in #64 (comment)

mex functions fail to compile with MATLAB R2018a

The following error occurs when compiling the mex functions using MATLAB R2018a

set (CMAKE_C_FLAGS "${CMAKE_C_FLAGS} -std=c99 -Wall -Wextra -pedantic -Werror=implicit-function-declaration")

Removing the gcc flag -Werror=implicit-function-declaration makes it compile fine, but when the function is called from MATLAB throws the following error:

Invalid MEX-file '/media/dataHD/downloads/browser/FNFT/matlab/mex_fnft_kdvv.mexa64': /media/dataHD/downloads/browser/FNFT/matlab/mex_fnft_kdvv.mexa64:
undefined symbol: mxGetPiIsDeprecated.

Inverse scattering

Start implementing inverse scattering routines.

FFTW problem

I am writing to share a solution to one problem. If you have the following error during compilation:

usr/bin/ld: /usr/local/lib/libfftw3.a(assert.o): relocation R_X86_64_PC32 against symbol `stdout@@GLIBC_2.2.5' can not be used when making a shared object; recompile with -fPIC

when you compile with the -DENABLE_FFTW=ON flag, then you have to rebuild the FFTW library with the --enable-shared flag. And then rebuild FNFT library.

Problems with installing gcc from scoop

As reported in this issues: [https://github.com/ScoopInstaller/Main/issues/1752], some of the mirror links related to installing gcc in the scoop is no longer accessible, is there any other ways of installing gcc?

Adaptive subsampling factor

Let users change the subsampling factor used for computing initial guesses for bound states.

Usage of const variables

There are several functions, where variables are declared, assigned a few lines later and not reassigned later on. E.g. the variable eps_t in refine_roots_newton:

    REAL re_bound_val, im_bound_val, eps_t;
    UINT trunc_index;
    trunc_index = D;
    eps_t = (T[1] - T[0])/(D - 1);

Does it respect your style if refactored as follows?

    REAL re_bound_val, im_bound_val;
    UINT trunc_index;
    trunc_index = D;
    const REAL eps_t = (T[1] - T[0])/(D - 1);

Thread_local detected but not supported by C99

CMake is detecting Thread_local:

-- The C compiler identification is GNU 6.4.0
[..]
-- Performing Test HAVE__THREAD_LOCAL
-- Performing Test HAVE__THREAD_LOCAL - Success

Anyway, C99 does not support it:

[  0%] Building C object CMakeFiles/fnft.dir/src/fnft_errwarn.c.o
/home/brehler/Development/FNFT/src/fnft_errwarn.c:44:1: warning: ISO C99 does not support ‘_Thread_local’ [-Wpedantic]
 _Thread_local

Docstring for fnft_nsev_cstype_t is incomplete

Hello,
the docstring for fnft_nsev_cstype_t in FNFT/include/fnft_nsev.h is incomplete:

it describes

• fnft_nsev_cstype_REFLECTION_COEFFICIENT
• fnft_nsev_cstype_AB

but there is not description for the third option,

• fnft_nsev_cstype_BOTH

which should affect the size of contspec array that should be submitted

regards, Christoph

fnft_nsev_inverse fails if D is not a power of 2

Is this a bug or the intended behavior? In the second case it would be good to add this fact to the documentation.

Run:
q = mex_fnft_nsev_inverse([], [-1 1], [1i*0.3], [1i], 1023, [-1 1], 1 )

Error:

FNFT Error: Invalid argument D.
 in fnft_nsev_inverse(148)-0.2.1

Make M>>D in fnft_nsev possible

Currently, only M<=2D is guaranteed to work.

Inverse NFT of discrete spectrum for NSE

Ability to compute multi-soliton solutions of NSE given eigenvalues and norming constants/spectral amplitudes. Adding solitonic components to any non-solitonic seed solution.

support for M1 chip architecture on macOS

Hey,
I'm trying to run my FNFT python project on my macbook which has M1 chip.

I've managed to install brew cmake and gcc (the latest gcc v11 not 7 as said).
and also to build using:
CC=gcc FC=gfortran cmake ..

and 159/160 tests passed, number 14 failed:
14/160 Test #14: fnft__akns_fscatter_test_2split6A .................................***Failed 0.44 sec

when I execute my python code (edited the auxilary path to lib/libfnft.0.4.1.dylib (tried all 3 *dylib files) I get the following error:

OSError: dlopen(//lib/libfnft.0.dylib, 6): no suitable image found. Did find:
//lib/libfnft.0.dylib: mach-o, but wrong architecture
//lib/libfnft.0.4.1.dylib: mach-o, but wrong architecture

Any chance to get a workaround or M1 support?

eps_t unused in private/fnft__nsep_testcases.c

Taking a deeper look into the code, I noticed that eps_t is initialized as

FNFT/src/private/fnft__nsep_testcases.c

Line 187 in bcd8767

eps_t = (T[1] - T[0])/D; // location of last sample is T[1]-eps_t

However, eps_t seems not to be used afterwards.

FNFT when input is A sech(t), where A = N+1/2 (N = 1, 2, 3,... )

Hello Dr. Sander Wahls, I find when the input waveform Asech(t) has amplitude A = 1.5, or 2.5, 3.5..., as shown in the figures below, the continuous spectrum is extremely high, which seems strange as this may violate the Parseval Identity for NFT, and if these FNFT results are fed into iFNFT, it won't return the original waveform (this also happens when A is close to 1.5).

So A = N+1/2 (N = 1, 2, 3,... ) seems to be a critical number? but many references only give the NFT result when A = N and N+|α| (α<1/2) there is a ref. I'm not sure what the NFT result should be theoretically in "A = N+1/2" cases. Could you please have a look at it? Thanks a lot.

`akns_scatter_matrix` implementation not speed-optimal.

• commit dbc8896: misc_mat_mul_proto was not indented to be called directly; instead the idea is to create a new function of the form fnft__misc_matrix_mult_MxN (with M,N actual numbers) so that the compiler can take the a priori known matrix size into account. Were there any special reason for not doing that here?

With fixed matrix sizes we would need to add 5 separate functions, namely for 2x2 times 2x2, 4x4 times 4x4, 2x2 times 2x4, 2x2 times 2x1 and 4x4 times 4x1. Since the matrix size inputs to fnft__misc_matrix_mult are constants, and since the function is only used with hard coded inputs (for the sizes), the compiler still knows the sizes a priory. Also note that there is no memory allocation inside fnft__misc_matrix_mult that would slow down in the case of variable sizes. A further consideration for this implementation is that it prevents the repeated calls to memcpy, one for every sample of the potential.

I've compared the speed between the implementation before this pull request and a version after this commit and it appears to make no measurable difference. Hence, the implementation with 5 separate functions has no advantage regarding the performance, whereas it does have the disadvantages of code copying.

Correction: I've tried to reproduce that test, but got a different result. (Probably there was a problem with multiple versions in the Matlab path last time.) It now appears that 1a69d18 caused a 7 to 15% longer runtime for all slow NSE algorithms. Adding and using separate multiplication functions for each matrix size to 07bd054 doesn't make any difference, though. I'll search for the cause and solution and get back to this.

Originally posted by @PJ-Prins in #64 (comment)