Regensburg 2022 – scientific programme

Parts | Days | Selection | Search | Updates | Downloads | Help

TT: Fachverband Tiefe Temperaturen

TT 16: Correlated Electrons: Method Development

TT 16.12: Talk

Wednesday, September 7, 2022, 12:45–13:00, H10

Trie-based ranking of quantum many-body states — •Markus Wallerberger and Karsten Held — TU Wien, Vienna, Austria

Ranking bit patterns -- finding the index of a given pattern in an ordered sequence -- is a major bottleneck scaling up numerical quantum many-body calculations, as fermionic and hard-core bosonic states translate naturally to bit patterns. Traditionally, ranking is done by bisectioning search, which has poor cache performance on modern machines.

We instead propose to use tries (prefix trees), thereby achieving a two- to ten-fold speed-up in numerical experiments with only moderate memory overhead. For the important problem of ranking permutations, the corresponding tries can be compressed. These compressed ``staggered'' lookups allow for an additional speed-up while retaining the memory requirements of prior algorithms based on the combinatorial number system.

We use these improvements to go to larger system sizes for which three-and four-point propagators can be computed.