Minimizing Communication for Parallel Symmetric Tensor Times Same Vector Computation
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909652533379072 |
|---|---|
| author | Daas, Hussam Al Ballard, Grey Grigori, Laura Kumar, Suraj Rouse, Kathryn Vérité, Mathieu |
| author_facet | Daas, Hussam Al Ballard, Grey Grigori, Laura Kumar, Suraj Rouse, Kathryn Vérité, Mathieu |
| contents | In this article, we focus on the parallel communication cost of multiplying the same vector along two modes of a $3$-dimensional symmetric tensor. This is a key computation in the higher-order power method for determining eigenpairs of a $3$-dimensional symmetric tensor and in gradient-based methods for computing a symmetric CP decomposition. We establish communication lower bounds that determine how much data movement is required to perform the specified computation in parallel. The core idea of the proof relies on extending a key geometric inequality for $3$-dimensional symmetric computations. We demonstrate that the communication lower bounds are tight by presenting an optimal algorithm where the data distribution is a natural extension of the triangle block partition scheme for symmetric matrices to 3-dimensional symmetric tensors. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_15488 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Minimizing Communication for Parallel Symmetric Tensor Times Same Vector Computation Daas, Hussam Al Ballard, Grey Grigori, Laura Kumar, Suraj Rouse, Kathryn Vérité, Mathieu Distributed, Parallel, and Cluster Computing In this article, we focus on the parallel communication cost of multiplying the same vector along two modes of a $3$-dimensional symmetric tensor. This is a key computation in the higher-order power method for determining eigenpairs of a $3$-dimensional symmetric tensor and in gradient-based methods for computing a symmetric CP decomposition. We establish communication lower bounds that determine how much data movement is required to perform the specified computation in parallel. The core idea of the proof relies on extending a key geometric inequality for $3$-dimensional symmetric computations. We demonstrate that the communication lower bounds are tight by presenting an optimal algorithm where the data distribution is a natural extension of the triangle block partition scheme for symmetric matrices to 3-dimensional symmetric tensors. |
| title | Minimizing Communication for Parallel Symmetric Tensor Times Same Vector Computation |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2506.15488 |