Trie-based ranking of quantum many-body states
Ranking bit patterns—finding the index of a given pattern in an ordered sequence—is a major bottleneck in 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 h...
| প্রধান লেখক: | , |
|---|---|
| বিন্যাস: | প্রবন্ধ |
| ভাষা: | English |
| প্রকাশিত: |
American Physical Society
2022-09-01
|
| মালা: | Physical Review Research |
| অনলাইন ব্যবহার করুন: | http://doi.org/10.1103/PhysRevResearch.4.033238 |
| _version_ | 1827285367916593152 |
|---|---|
| author | Markus Wallerberger Karsten Held |
| author_facet | Markus Wallerberger Karsten Held |
| author_sort | Markus Wallerberger |
| collection | DOAJ |
| description | Ranking bit patterns—finding the index of a given pattern in an ordered sequence—is a major bottleneck in 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 tenfold speedup 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 a considerable speedup while retaining the memory requirements of prior algorithms based on the combinatorial number system. |
| first_indexed | 2024-04-24T10:13:28Z |
| format | Article |
| id | doaj.art-024a9ea74d314c9ebf825c49f0eed7a3 |
| institution | Directory Open Access Journal |
| issn | 2643-1564 |
| language | English |
| last_indexed | 2024-04-24T10:13:28Z |
| publishDate | 2022-09-01 |
| publisher | American Physical Society |
| record_format | Article |
| series | Physical Review Research |
| spelling | doaj.art-024a9ea74d314c9ebf825c49f0eed7a32024-04-12T17:24:47ZengAmerican Physical SocietyPhysical Review Research2643-15642022-09-014303323810.1103/PhysRevResearch.4.033238Trie-based ranking of quantum many-body statesMarkus WallerbergerKarsten HeldRanking bit patterns—finding the index of a given pattern in an ordered sequence—is a major bottleneck in 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 tenfold speedup 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 a considerable speedup while retaining the memory requirements of prior algorithms based on the combinatorial number system.http://doi.org/10.1103/PhysRevResearch.4.033238 |
| spellingShingle | Markus Wallerberger Karsten Held Trie-based ranking of quantum many-body states Physical Review Research |
| title | Trie-based ranking of quantum many-body states |
| title_full | Trie-based ranking of quantum many-body states |
| title_fullStr | Trie-based ranking of quantum many-body states |
| title_full_unstemmed | Trie-based ranking of quantum many-body states |
| title_short | Trie-based ranking of quantum many-body states |
| title_sort | trie based ranking of quantum many body states |
| url | http://doi.org/10.1103/PhysRevResearch.4.033238 |
| work_keys_str_mv | AT markuswallerberger triebasedrankingofquantummanybodystates AT karstenheld triebasedrankingofquantummanybodystates |