Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Fast sparse matrix multiplication

Fast sparse matrix multiplication Let A and B two n × n matrices over a ring R (e.g., the reals or the integers) each containing at most m nonzero elements. We present a new algorithm that multiplies A and B using O ( m 0.7 n 1.2 + n 2+ o (1) ) algebraic operations (i.e., multiplications, additions and subtractions) over R . The naïve matrix multiplication algorithm, on the other hand, may need to perform Ω( mn ) operations to accomplish the same task. For m ≤ n 1.14 , the new algorithm performs an almost optimal number of only n 2+ o (1) operations. For m ≤ n 1.68 , the new algorithm is also faster than the best known matrix multiplication algorithm for dense matrices which uses O ( n 2.38 ) algebraic operations. The new algorithm is obtained using a surprisingly straightforward combination of a simple combinatorial idea and existing fast rectangular matrix multiplication algorithms. We also obtain improved algorithms for the multiplication of more than two sparse matrices. As the known fast rectangular matrix multiplication algorithms are far from being practical, our result, at least for now, is only of theoretical value. http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Algorithms (TALG) Association for Computing Machinery

Fast sparse matrix multiplication

Download PDF
12 pages

Loading next page...
 
/lp/association-for-computing-machinery/fast-sparse-matrix-multiplication-tvwGEh8fDm
Publisher
Association for Computing Machinery
Copyright
Copyright © 2005 by ACM Inc.
ISSN
1549-6325
DOI
10.1145/1077464.1077466
Publisher site
See Article on Publisher Site

Abstract

Let A and B two n × n matrices over a ring R (e.g., the reals or the integers) each containing at most m nonzero elements. We present a new algorithm that multiplies A and B using O ( m 0.7 n 1.2 + n 2+ o (1) ) algebraic operations (i.e., multiplications, additions and subtractions) over R . The naïve matrix multiplication algorithm, on the other hand, may need to perform Ω( mn ) operations to accomplish the same task. For m ≤ n 1.14 , the new algorithm performs an almost optimal number of only n 2+ o (1) operations. For m ≤ n 1.68 , the new algorithm is also faster than the best known matrix multiplication algorithm for dense matrices which uses O ( n 2.38 ) algebraic operations. The new algorithm is obtained using a surprisingly straightforward combination of a simple combinatorial idea and existing fast rectangular matrix multiplication algorithms. We also obtain improved algorithms for the multiplication of more than two sparse matrices. As the known fast rectangular matrix multiplication algorithms are far from being practical, our result, at least for now, is only of theoretical value.

Journal

ACM Transactions on Algorithms (TALG) – Association for Computing Machinery

Published: Jul 1, 2005

There are no references for this article.