2023/10/24 by Tianyu Liang, Liang, Tianyu, Riley Murray +5
Computer Science · #Complexity and Algorithms in Graphs #Computational Engineering #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Finance #Optimization and Search Problems #Parallel #Stochastic Gradient Optimization Techniques #and Cluster Computing (cs.DC) #and Science (cs.CE)
paper · pdf · doi:10.48550/arxiv.2310.15419
openalex publication_date 2023/10/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/30
This work focuses on accelerating the multiplication of a dense random matrix with a (fixed) sparse matrix, which is frequently used in sketching algorithms. We develop a novel scheme that takes advantage of blocking and recomputation (on-the-fly random number generation) to accelerate this operation. The techniques we propose decrease memory movement, thereby increasing the algorithm's parallel scalability in shared memory architectures. On the Intel Frontera architecture, our algorithm can achieve 2x speedups over libraries such as Eigen and Intel MKL on some examples. In addition, with 32 threads, we can obtain a parallel efficiency of up to approximately 45%. We also present a theoretical analysis for the memory movement lower bound of our algorithm, showing that under mild assumptions, it's possible to beat the data movement lower bound of general matrix-matrix multiply (GEMM) by a factor of √ M, where M is the cache size. Finally, we incorporate our sketching algorithm into a randomized least squares solver. For extremely over-determined sparse input matrices, we show that our results are competitive with SuiteSparse; in some cases, we obtain a speedup of 10x over SuiteSparse.