BetheSF: Efficient computation of the exact tagged-particle propagator in single-file systems via the Bethe eigenspectrum

Single-file diffusion is a paradigm for strongly correlated classical stochastic many-body dynamics and has widespread applications in soft condensed matter and biophysics. However, exact results for single-file systems are sparse and limited to the simplest scenarios. We present an algorithm for computing the non-Markovian time-dependent conditional probability density function of a tagged-particle in a single-file of N particles diffusing in a confining external potential. The algorithm implements an eigenexpansion of the full interacting many-body problem obtained by means of the coordinate Bethe ansatz. While formally exact, the Bethe eigenspectrum involves the generation and evaluation of permutations, which becomes unfeasible for single-files with an increasing number of particles N. Here we exploit the underlying exchange symmetries between the particles to the left and to the right of the tagged-particle and show that it is possible to reduce the complexity of the algorithm from the worst case scenario O(N!) down to O(N). A C++ code to calculate the non-Markovian probability density function using this algorithm is provided. Solutions for simple model potentials are readily implemented including single-file diffusion in a flat and a 'tilted' box, as well as in a parabolic potential. Notably, the program allows for implementations of solutions in arbitrary external potentials under the condition that the user can supply solutions to the respective single-particle eigenspectra. Program summary Program Title: BetheSF CPC Library link to program files: http://dx.doi.org/10.17632/3bs74vf72n.1 Licensing provisions: MIT Programming language: C++ (C++17 support required) Supplementary material: makefile, README, SingleFileBluePrint.hpp Nature of problem: Diffusive single-files are mathematical models of effectively one-dimensional strongly correlated many-body systems. While the dynamics of the full system is Markovian, the diffusion of a tracer-particle in a single-file is an example of non-Markovian and anomalous diffusion. The many-body Fokker-Planck equation governing the system's dynamics can be solved using the coordinate Bethe ansatz. A naive implementation of such a solution runs in non-polynomial time since it requires the generation of permutations of the elements of a multiset. Solution method: In this paper we show how, exploiting the exchange symmetries of the system, it is possible to reduce the complexity of the algorithm to evaluate the solution, using a permutationgeneration algorithm, from O(N!) in the worst case scenario to O(N) in the best case scenario, which corresponds to tagging the first or the last particle, where N stands for the number of particles in the single-file. Additional comments including restrictions and unusual features: The code may overflow for large single-files N >= 170. All the benchmarks ran on the following CPU: Intel Xeon E3-1270 v2 3.50 GHz 4 cores. The compiler used is g++ 7.3.1 (SUSE Linux) with the optimization-O3 turned on. The code to produce all the data in the figures is included in the files: figure2.cpp, figure3.cpp, figure4.cpp, figure5a.cpp and figure5b.cpp (C) 2020 Elsevier B.V. All rights reserved.

Automated summary

The paper introduces an algorithm for computing the non-Markovian time-dependent conditional probability density function of a tagged-particle in a single-file system of N diffusing particles. By implementing an eigenexpansion through the coordinate Bethe ansatz, the algorithm reduces the complexity from O(N!) to O(N) by exploiting exchange symmetries between the particles.