Optimizing Tensor Contraction Paths: A Greedy Algorithm Approach With Improved Cost Functions
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866909205302083584 |
|---|---|
| author | Orgler, Sheela Blacher, Mark |
| author_facet | Orgler, Sheela Blacher, Mark |
| contents | Finding efficient tensor contraction paths is essential for a wide range of problems, including model counting, quantum circuits, graph problems, and language models. There exist several approaches to find efficient paths, such as the greedy and random greedy algorithm by Optimized Einsum (opt_einsum), and the greedy algorithm and hypergraph partitioning approach employed in cotengra. However, these algorithms require a lot of computational time and resources to find efficient contraction paths. In this paper, we introduce a novel approach based on the greedy algorithm by opt_einsum that computes efficient contraction paths in less time. Moreover, with our approach, we are even able to compute paths for large problems where modern algorithms fail. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_09644 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimizing Tensor Contraction Paths: A Greedy Algorithm Approach With Improved Cost Functions Orgler, Sheela Blacher, Mark Quantum Physics Discrete Mathematics Mathematical Software Finding efficient tensor contraction paths is essential for a wide range of problems, including model counting, quantum circuits, graph problems, and language models. There exist several approaches to find efficient paths, such as the greedy and random greedy algorithm by Optimized Einsum (opt_einsum), and the greedy algorithm and hypergraph partitioning approach employed in cotengra. However, these algorithms require a lot of computational time and resources to find efficient contraction paths. In this paper, we introduce a novel approach based on the greedy algorithm by opt_einsum that computes efficient contraction paths in less time. Moreover, with our approach, we are even able to compute paths for large problems where modern algorithms fail. |
| title | Optimizing Tensor Contraction Paths: A Greedy Algorithm Approach With Improved Cost Functions |
| topic | Quantum Physics Discrete Mathematics Mathematical Software |
| url | https://arxiv.org/abs/2405.09644 |