A Simple Sparse Matrix Vector Multiplication Approach to Padded Convolution

Autor:	Chaudhry, Zan
Rok vydání:	2024
Předmět:	Computer Science - Machine Learning Computer Science - Data Structures and Algorithms
Druh dokumentu:	Working Paper
Popis:	We introduce an algorithm for efficiently representing convolution with zero-padding and stride as a sparse transformation matrix, applied to a vectorized input through sparse matrix-vector multiplication (SpMV). We provide a theoretical contribution with an explicit expression for the number of non-zero multiplications in convolutions with stride and padding, offering insight into the potential for leveraging sparsity in convolution operations. A proof-of-concept implementation is presented in Python, demonstrating the performance of our method on both CPU and GPU architectures. This work contributes to the broader exploration of sparse matrix techniques in convolutional algorithms, with a particular focus on leveraging matrix multiplications for parallelization. Our findings lay the groundwork for future advancements in exploiting sparsity to improve the efficiency of convolution operations in fields such as machine learning and signal processing. Comment: 10 pages, 2 figures, 2 tables
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2411.19419 Zobrazit plný text záznamu View this record from Arxiv