Gespeichert in:
| Hauptverfasser: | , , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2026
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2603.04829 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914370263449600 |
|---|---|
| author | Krengel, Dominik Watanabe, Yuki Kandori, Ko Chen, Jian Matuttis, Hans-Georg |
| author_facet | Krengel, Dominik Watanabe, Yuki Kandori, Ko Chen, Jian Matuttis, Hans-Georg |
| contents | Neighborhood algorithms may take a considerable percentage of computer time in discrete element methods (DEM). While the sort-and-sweep algorithm is ideal in some ways, as it only deal with particles whose relative positions change in one coordinate direction, the other directions must be processed too, for all particles. In contrast, tree-codes deal only with adjacent particles. We compare sort-and-sweep and tree-code neighborhood algorithms for two-dimensional DEM simulations of polygonal particles in a rotating drum with up to 12000 particles. We discuss the effects of system size and inlining on the performance with respect to the cache memory. For the tree code, the performance is slightly better, at the cost of significantly increased cyclomatic complexity. In particular, one benefit is improved possibilities for shared memory parallelization. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_04829 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Tree codes and sort-and-sweep algorithms for neighborhood computation: A cache-conscious comparison Krengel, Dominik Watanabe, Yuki Kandori, Ko Chen, Jian Matuttis, Hans-Georg Computational Physics Neighborhood algorithms may take a considerable percentage of computer time in discrete element methods (DEM). While the sort-and-sweep algorithm is ideal in some ways, as it only deal with particles whose relative positions change in one coordinate direction, the other directions must be processed too, for all particles. In contrast, tree-codes deal only with adjacent particles. We compare sort-and-sweep and tree-code neighborhood algorithms for two-dimensional DEM simulations of polygonal particles in a rotating drum with up to 12000 particles. We discuss the effects of system size and inlining on the performance with respect to the cache memory. For the tree code, the performance is slightly better, at the cost of significantly increased cyclomatic complexity. In particular, one benefit is improved possibilities for shared memory parallelization. |
| title | Tree codes and sort-and-sweep algorithms for neighborhood computation: A cache-conscious comparison |
| topic | Computational Physics |
| url | https://arxiv.org/abs/2603.04829 |