Efficient non-equidistant FFT approach to the measurement of single- and two-particle quantities in continuous time Quantum Monte Carlo methods

Continuous time cluster solvers allow us to measure single- and two-particle Greens functions in the Matsubara frequency domain with unprecedented accuracy. Currently, the usage of the two-particle functions is limited due to a lack of an efficient measurement method that can deal with the random times of the vertices. In this paper, we show how the Non-equidistant Fast Fourier Transform (NFFT) algorithm can be modified in order to obtain a very efficient measurement algorithm. For the single particle case, we propose a delayed-NFFT (d-NFFT) scheme, which reduces the arithmetical operations from O(N log(N)) in NFFT to O(N), a huge improvement compared to the standard O(N2) of the Non-equidistant Discrete Fourier Transform (NDFT), currently used in most continuous time cluster solvers. For the two-particle case, we discuss how the NFFT can be applied to measure the two-particle Greens functions and how to exploit its properties to further optimize the NFFT. We then apply these algorithms to the half-filled 2D Hubbard model at U/t = 8 in order to study the anti-ferromagnetic transition. In particular, we confirm the logarithmic decay of the Neel-temperatures versus cluster-sizes in accordance with the Mermin-Wagner theorem.