SLMC-CT-AUX

Demo for an efficient method for SLMC CT-AUX update proposed in our paper:

• Ruixiao Cao and Synge Todo, "Fast-update in self-learning algorithm for continuous-time quantum Monte Carlo," arXiv:2106.11645,

which improves the time complexity of the SLMC algorithm proposed in this paper.

This demo shows an algorithm to do simulation on SLMC of CT-AUX model more efficiently, where the asymptotic time complexity for one step decreases from O(nm) to O(m^2 + m logn).

To compile this demo, you need CMake (version 3.1 or higher) and a C++14 compiler.

To run this demo, do the following after cloning this demo and entering the directory:

mkdir build
cd build
cmake ..
make
./SLMC-demo

SLMC-demo is a test run for the algorithm generated by splayTest.cpp. It runs simulations over a set of values for n, from 10 to 3000, and compares the CPU time cost between original O(nm) and proposed O(m^2 + m logn) algorithms. It can be found that when n is large enough(which corresponds to low enough temperature), our technique is definitely faster than the original algorithm.

By modifying the parameters in splayTest.cpp, more cases can be tested: the order for J, L, and f functions can be modified by mJ, mL, mF. The range of tau can be modified by beta. Try it out and find the speedup for large n!