Lazy skip-lists: An algorithm for fast hybridization-expansion quantum Monte Carlo

The solution of a generalized impurity model lies at the heart of electronic structure calculations with dynamical mean field theory. In the strongly correlated regime, the method of choice for solving the impurity model is the hybridization-expansion continuous-time quantum Monte Carlo (CT-HYB). Enhancements to the CT-HYB algorithm are critical for bringing new physical regimes within reach of current computational power. Taking advantage of the fact that the bottleneck in the algorithm is a product of hundreds of matrices, we present optimizations based on the introduction and combination of two concepts of more general applicability: (a) skip lists and (b) fast rejection of proposed configurations based on matrix bounds. Considering two very different test cases with $d$ electrons, we find speedups of $\sim 25$ up to $\sim 500$ compared to the direct evaluation of the matrix product. Even larger speedups are likely with $f$ electron systems and with clusters of correlated atoms.

Figure 1

Benchmark of different optimizations presented in this paper on the basis of a LNO thin film simulation [27] (top panel) and a FeTe simulation (lower panel), using standard updates with low acceptance ratio and efficient updates with high acceptance ratio. We measure the speedup of the skip lists (Sec. 5a without lazy-trace evaluation), the lazy-trace evaluation (Sec. 4), and the lazy skip-lists (Secs. 5a and 5b), compared to a straightforward implementation (Sec. 2b) as baseline.

Figure 2

Top panel: Storage scheme for subproducts of matrices. The arrows store the products of matrices they span over. The $l=1$ level stores the pair products, the $l=2$ their products, and so on. Lower panel: The matrix $F$ has been inserted in the matrix product of the top panel and the products with a bold red multiplication sign need to be calculated in order to obtain the total product.

Figure 3

Skip list to store subproducts of operators $F_i$ and propagators $P$. The arrows store the products they span over. The bold arrows in red and green show the path that is followed when a matrix is inserted at the place indicated by the red triangle. The products stored in the blue arrows are emptied if their tail coincides with that of the bold red arrows.

Figure 4

The bounding technique within the lazy-trace evaluation. We first flip a coin to obtain a random number $u\in [0,1]$. Then, using submultiplicative matrix norms, we compute initial bounds $p_{\min }<p<p_{\max }$ on the acceptance probability. The bounds are refined until $u$ falls outside $[p_{\min },p_{\max }]$ and the move can be definitively accepted or rejected.

Figure 5

Benchmark of different optimizations presented in this paper on the basis of a LNO thin film simulation (a) and a FeTe simulation (b): using efficient updates with high acceptance ratio (top panel) and standard updates with low acceptance (lower panel). We measure speedup, reduction in matrix multiplications, and reduction in floating-point operations within matrix multiplications, with a straightforward implementation (Sec. 2b) as baseline.

Figure 6

On the basis of a LNO thin film simulation (a) and of a FeTe simulation (b) with standard updates: average weight $\langle {\mathrm{Tr}}_q/\mathrm{Tr}\rangle$ of a sector $q$ in the partition function expansion (top panel) and frequency with which ${\mathrm{Tr}}_q$ is calculated for a sector (lower panel).