Communication Lower Bounds and Algorithms for Sketching with Random Dense Matrices
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912977459871744 |
|---|---|
| author | Daas, Hussam Al Ballard, Grey Grigori, Laura Hussain, Md Taufique Kumar, Suraj Rahman, Mohammad Marufur Rouse, Kathryn |
| author_facet | Daas, Hussam Al Ballard, Grey Grigori, Laura Hussain, Md Taufique Kumar, Suraj Rahman, Mohammad Marufur Rouse, Kathryn |
| contents | Sketching is widely used in randomized linear algebra for low-rank matrix approximation, column subset selection, and many other problems, and it has gained significant traction in machine learning applications. However, sketching large matrices often necessitates distributed memory algorithms, where communication overhead becomes a critical bottleneck on modern supercomputing clusters. Despite its growing relevance, distributed-memory parallel strategies for sketching remain largely unexplored. In this work, we establish communication lower bounds for sketching using dense matrices that determine how much data movement is required to perform it in parallel. One important observation of our lower bounds is that no communication is required for a small number of processors. We show that our lower bounds are tight by presenting communication optimal algorithms. Furthermore, we extend our approach to determine communication lower bounds for computations of Nyström approximation where sketching is applied twice. We also introduce novel parallel algorithms whose communication costs are close to the lower bounds. Finally, we implement our algorithms on modern state-of-the-art supercomputing infrastructures which have both CPU- and GPU-equipped systems and demonstrate their parallel scalability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_20966 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Communication Lower Bounds and Algorithms for Sketching with Random Dense Matrices Daas, Hussam Al Ballard, Grey Grigori, Laura Hussain, Md Taufique Kumar, Suraj Rahman, Mohammad Marufur Rouse, Kathryn Distributed, Parallel, and Cluster Computing Sketching is widely used in randomized linear algebra for low-rank matrix approximation, column subset selection, and many other problems, and it has gained significant traction in machine learning applications. However, sketching large matrices often necessitates distributed memory algorithms, where communication overhead becomes a critical bottleneck on modern supercomputing clusters. Despite its growing relevance, distributed-memory parallel strategies for sketching remain largely unexplored. In this work, we establish communication lower bounds for sketching using dense matrices that determine how much data movement is required to perform it in parallel. One important observation of our lower bounds is that no communication is required for a small number of processors. We show that our lower bounds are tight by presenting communication optimal algorithms. Furthermore, we extend our approach to determine communication lower bounds for computations of Nyström approximation where sketching is applied twice. We also introduce novel parallel algorithms whose communication costs are close to the lower bounds. Finally, we implement our algorithms on modern state-of-the-art supercomputing infrastructures which have both CPU- and GPU-equipped systems and demonstrate their parallel scalability. |
| title | Communication Lower Bounds and Algorithms for Sketching with Random Dense Matrices |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2603.20966 |