Fast principal minor algorithms for diagrammatic Monte Carlo

The computation of determinants plays a central role in diagrammatic Monte Carlo algorithms for strongly correlated systems. The evaluation of large numbers of determinants can often be the limiting computational factor determining the number of attainable diagrammatic expansion orders. In this work we build on the algorithm presented in [K. Griffin and M. J. Tsatsomeros, Principal minors, part i: A method for computing all the principal minors of a matrix, Linear Algebra Appl. 419, 107 (2006)0024-379510.1016/j.laa.2006.04.008] which computes all principal minors of a matrix in O(2n) operations. We present multiple generalizations of the algorithm to the efficient evaluation of certain subsets of all principal minors with immediate applications to connected determinant diagrammatic Monte Carlo within the normal and symmetry-broken phases as well as continuous-time quantum Monte Carlo. Additionally, we improve the asymptotic scaling of diagrammatic Monte Carlo formulated in real time to O(2n) and report speedups of up to a factor 25 at computationally realistic expansion orders. We further show that all permanent principal minors, corresponding to sums of bosonic Feynman diagrams, can be computed in O(3n), thus encouraging the investigation of bosonic and mixed systems by means of diagrammatic Monte Carlo.