Communication Lower Bounds and Algorithms for Sketching with Random Dense Matrices

Hussam Al Daas, Grey Ballard, Laura Grigori, Md Taufique Hussain, Suraj Kumar, Mohammad Marufur Rahman, Kathryn Rouse · 2026

Read Communication Lower Bounds and Algorithms for Sketching with Random Dense Matrices by Hussam Al Daas, Grey Ballard, Laura Grigori, Md Taufique Hussain, Suraj Kumar, Mohammad Marufur Rahman, Kathryn Rouse (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-20966.txt.

Introduction

Al Daas and co-authors set communication lower bounds for sketching with random dense matrices. Sketching supports low rank approximation and column subset selection, and is widely used in machine learning. On distributed machines, moving data is often the main cost, yet parallel sketching was little studied. They prove how much data movement any parallel method needs. They give algorithms that meet the bounds, and extend the results to Nyström approximation. Their code scales well on modern CPU and GPU clusters.

Catalog record

CREATORHussam Al Daas, Grey Ballard, Laura Grigori, Md Taufique Hussain, Suraj Kumar, Mohammad Marufur Rahman, Kathryn Rouse
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE69628
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.20966

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Communication Lower Bounds and Algorithms for Sketching with Random Dense Matrices Hussam Al Daas, Grey Ballard, Laura Grigori, Md Taufique Hussain, Suraj Kumar, Mohammad Marufur Rahman, Kathryn Rouse Abstract . 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. 1. Introduction Many important linear algebra problems, such as computing low-rank approximations of a matrix, selecting a subset of its columns, solving linear systems, or computing eigenvalue decompositions, can be efficiently solved using randomization techniques that allow reducing computational and communication costs while providing accuracy guarantees with high probability, see ( Cortinovis and Kressner 2026 ; Bucci et al. 2025 ; Balabanov and Grigori 2022 ; Frangella et al. 2023 ) . These techniques rely on sketching , a dimensionality reduction approach in which a matrix {\bm{\mathbf{{A}}}}\in\mathbb{R}^{n_{1}\times n_{2}} is mapped to a lower-dimensional representation by multiplying it with a random matrix {\bm{\mathbf{{\Omega}}}}\in\mathbb{R}^{n_{2}\times r} , where generally r\ll n_{2} . Depending on the application, the matrix {\bm{\mathbf{{A}}}} may have different dimensions and aspect ratios. Different random matrices can be used for sketching, including Gaussian matrices, structured fast transforms, and sparse random matrices. In this work, we focus on dense random matrices including Gaussian random matrices, which offer optimal theoretical guarantees for constructing low-dimensional representations. We refer the reader to ( Martinsson and Tropp 2020 ) for a comprehensive overview of these sketching methods and their associated properties. The goal of this work is to design efficient parallel algorithms for computing the product {\bm{\mathbf{{A}}}}{\bm{\mathbf{{\Omega}}}} , with a particular focus of avoiding unnecessary communication of random matrices. Because each processor can redundantly generate its needed entries of the random matrix, these products can be computed without communicating the random matrix, decreasing the amount of communication required from that of an explicit matrix multiplication (see, e.g., ( Al Daas et al. 2022 ) ). We then focus on an application of sketching to the Nyström approximation that computes a low rank approximation of a symmetric square matrix {\bm{\mathbf{{A}}}} as \widetilde{{\bm{\mathbf{{A}}}}}=({\bm{\mathbf{{A}}}}{\bm{\mathbf{{\Omega}}}})({\bm{\mathbf{{\Omega}}}}^{T}{\bm{\mathbf{{A}}}}{\bm{\mathbf{{\Omega}}}})^{\dagger}({\bm{\mathbf{{A}}}}{\bm{\mathbf{{\Omega}}}})^{T} ( Nyström 1930 ; Williams and Seeger 2000 ; Gittens and Mahoney 2016a ) , for some random matrix {\bm{\mathbf{{\Omega}}}} . This representation involves first computing {\bm{\mathbf{{B}}}}={\bm{\mathbf{{A}}}}{\bm{\mathbf{{\Omega}}}} and then computing {\bm{\mathbf{{C}}}}={\bm{\mathbf{{\Omega}}}}^{T}{\bm{\mathbf{{B}}}} . We address this question theoretically, establishing communication lower bounds and analyzing asymptotic algorithmic costs, as well as practically implementing the most communication efficient algorithms and applying them to large data sets on 100s of nodes (100s of GPUs or 1000s of CPU cores) of a supercomputer. Our lower bound approach uses a geometric inequality that relates computation to data to build a constrained optimization problem whose analytical solution yields communication lower bounds. We consider both a single matrix multiplication involving a random input as well as the entire Nyström computation. We develop implementations using both Python and C++ and adapt them for both CPU-only and GPU platforms and explore the performance tradeoffs among the various configurations. Our results show the benefits of GPUs for performing dense matrix multiplication to accelerate Nyström approximation and the effectiveness of direct communication among GPUs to scale to large problems, and we obtain low-rank approximations of symmetric matrices of dimension 50,000 in fractions of a second. Our code will be made publicly available. In this work, we focus on {\bm{\mathbf{{A}}}}{\bm{\mathbf{{\Omega}}}} and {\bm{\mathbf{{\Omega}}}}^{T}{\bm{\mathbf{{A}}}}{\bm{\mathbf{{\Omega}}}} computations for dense and random {\bm{\mathbf{{\Omega}}}} . The main contributions are to (1) establish communication lower bounds for the parallel computation of {\bm{\mathbf{{B}}}}={\bm{\mathbf{{A}}}}{\bm{\mathbf{{\Omega}}}} where {\bm{\mathbf{{\Omega}}}} is a dense random matrix and present parallel algorithms whose communication costs are optimal in all ranges (see section 4 ); (2) establish communication lower bounds for the parallel computation of the sequence of computations {\bm{\mathbf{{B}}}}={\bm{\mathbf{{A}}}}{\bm{\mathbf{{\Omega}}}} followed by {\bm{\mathbf{{C}}}}={\bm{\mathbf{{\Omega}}}}^{T}{\bm{\mathbf{{B}}}} where {\bm{\mathbf{{\Omega}}}} is a dense random matrix, and present parallel algorithms whose communication costs are close to the lower bounds (see section 5 ); (3) implement the most efficient algorithms using both Python and C++ for CPUs and GPUs (code to be made available) and benchmark the implementations to demonstrate the communication efficiency of the algorithms and their parallel scaling (see section 6 ). 2. Related Work There have been numerous studies on establishing communication lower bounds for matrix multiplication. The first bounds were proposed by Hong and Kung ( Hong and Kung 1981 ) for several computations including matrix multiplication. Aggarwal et al. ( Aggarwal et al. 1990 ) extended this work for the parallel model and established first memory-independent parallel communication lower bounds. Irony et al. ( Irony et al. 2004 ) reproduced the parallel matrix multiplication bounds using a geometric inequality. Al Daas et al. ( Al Daas et al. 2022 ) established tight parallel communication lower bounds for all ranges of matrix dimensions and numbers of processors. Liang et al. ( Liang et al. 2024 ) presented a theoretical analysis to determine the data transfer cost of their algorithm for multiplying a dense random matrix with a sparse matrix. Their algorithm performs less data movement than the classical GEMM bound. Balabanov et al. ( Balabanov et al. 2023 ) proposed a parallel sketching using a variant of the subsampled randomized Hadamard transform that exploits the structure of the random matrix. Talwalkar et al. ( Talwalkar et al. 2013 ) presented a parallel implementation of sketching and Nyström approximation applied to kernel matrices with very large datasets. Higgins et al. ( Higgins et al. 2025 ) presented a high performance GPU implementation of sketching using count sketch and its application to least squares problems. Chen et al. ( Chen et al. 2025 ) presented a parallel (multi GPU) implementation and a benchmark study of sparse sign sketching and its application to solve least squares problems. Nyström approximation has been considered for a wide range of random matrices. One of the most widely used techniques is based on random sampling. That is, the columns in {\bm{\mathbf{{\Omega}}}} are randomly selected from the identity matrix. The resulting Nyström approximation is given as \widetilde{{\bm{\mathbf{{A}}}}}={\bm{\mathbf{{A}}}}(:,c){\bm{\mathbf{{A}}}}(c,c)^{\dagger}{\bm{\mathbf{{A}}}}(:,c)^{T} , where c is the randomly selected subset of the column indices. This approximation is very easy to compute as it only requires access to a subset of the matrix entries and does not involve any matrix multiplication. However, the approximation quality can be very poor if c is not chosen carefully. Several sampling techniques relying on sketching have been investigated in

Read the complete text