Communication Lower Bounds and Optimal Algorithms for Symmetric Matrix Computations
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910608161505280 |
|---|---|
| author | Daas, Hussam Al Ballard, Grey Grigori, Laura Kumar, Suraj Rouse, Kathryn Verite, Mathieu |
| author_facet | Daas, Hussam Al Ballard, Grey Grigori, Laura Kumar, Suraj Rouse, Kathryn Verite, Mathieu |
| contents | In this article, we focus on the communication costs of three symmetric matrix computations: i) multiplying a matrix with its transpose, known as a symmetric rank-k update (SYRK) ii) adding the result of the multiplication of a matrix with the transpose of another matrix and the transpose of that result, known as a symmetric rank-2k update (SYR2K) iii) performing matrix multiplication with a symmetric input matrix (SYMM). All three computations appear in the Level 3 Basic Linear Algebra Subroutines (BLAS) and have wide use in applications involving symmetric matrices. We establish communication lower bounds for these kernels using sequential and distributed-memory parallel computational models, and we show that our bounds are tight by presenting communication-optimal algorithms for each setting. Our lower bound proofs rely on applying a geometric inequality for symmetric computations and analytically solving constrained nonlinear optimization problems. The symmetric matrix and its corresponding computations are accessed and performed according to a triangular block partitioning scheme in the optimal algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_11304 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Communication Lower Bounds and Optimal Algorithms for Symmetric Matrix Computations Daas, Hussam Al Ballard, Grey Grigori, Laura Kumar, Suraj Rouse, Kathryn Verite, Mathieu Distributed, Parallel, and Cluster Computing In this article, we focus on the communication costs of three symmetric matrix computations: i) multiplying a matrix with its transpose, known as a symmetric rank-k update (SYRK) ii) adding the result of the multiplication of a matrix with the transpose of another matrix and the transpose of that result, known as a symmetric rank-2k update (SYR2K) iii) performing matrix multiplication with a symmetric input matrix (SYMM). All three computations appear in the Level 3 Basic Linear Algebra Subroutines (BLAS) and have wide use in applications involving symmetric matrices. We establish communication lower bounds for these kernels using sequential and distributed-memory parallel computational models, and we show that our bounds are tight by presenting communication-optimal algorithms for each setting. Our lower bound proofs rely on applying a geometric inequality for symmetric computations and analytically solving constrained nonlinear optimization problems. The symmetric matrix and its corresponding computations are accessed and performed according to a triangular block partitioning scheme in the optimal algorithms. |
| title | Communication Lower Bounds and Optimal Algorithms for Symmetric Matrix Computations |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2409.11304 |