GPU-Parallelizable Randomized Sketch-and-Precondition for Linear Regression using Sparse Sign Sketches
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866908395860131840 |
|---|---|
| author | Chen, Tyler Niroula, Pradeep Ray, Archan Subrahmanya, Pragna Pistoia, Marco Kumar, Niraj |
| author_facet | Chen, Tyler Niroula, Pradeep Ray, Archan Subrahmanya, Pragna Pistoia, Marco Kumar, Niraj |
| contents | A litany of theoretical and numerical results have established the sketch-and-precondition paradigm as a powerful approach to solving large linear regression problems in standard computing environments. Perhaps surprisingly, much less work has been done on understanding how sketch-and-precondition performs on graphics processing unit (GPU) systems. We address this gap by benchmarking an implementation of sketch-and-precondition based on sparse sign-sketches on single and multi-GPU systems. In doing so, we describe a novel, easily parallelized, rejection-sampling based method for generating sparse sign sketches. Our approach, which is particularly well-suited for GPUs, is easily adapted to a variety of computing environments. Taken as a whole, our numerical experiments indicate that sketch-and-precondition with sparse sign sketches is particularly well-suited for GPUs, and may be suitable for use in black-box least-squares solvers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_03070 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | GPU-Parallelizable Randomized Sketch-and-Precondition for Linear Regression using Sparse Sign Sketches Chen, Tyler Niroula, Pradeep Ray, Archan Subrahmanya, Pragna Pistoia, Marco Kumar, Niraj Data Structures and Algorithms Distributed, Parallel, and Cluster Computing Numerical Analysis A litany of theoretical and numerical results have established the sketch-and-precondition paradigm as a powerful approach to solving large linear regression problems in standard computing environments. Perhaps surprisingly, much less work has been done on understanding how sketch-and-precondition performs on graphics processing unit (GPU) systems. We address this gap by benchmarking an implementation of sketch-and-precondition based on sparse sign-sketches on single and multi-GPU systems. In doing so, we describe a novel, easily parallelized, rejection-sampling based method for generating sparse sign sketches. Our approach, which is particularly well-suited for GPUs, is easily adapted to a variety of computing environments. Taken as a whole, our numerical experiments indicate that sketch-and-precondition with sparse sign sketches is particularly well-suited for GPUs, and may be suitable for use in black-box least-squares solvers. |
| title | GPU-Parallelizable Randomized Sketch-and-Precondition for Linear Regression using Sparse Sign Sketches |
| topic | Data Structures and Algorithms Distributed, Parallel, and Cluster Computing Numerical Analysis |
| url | https://arxiv.org/abs/2506.03070 |