## Abstract

We consider the problem of multiplying two $U \times U$ matrices $A$ and $C$ of elements from a field $\F$.

We present a new randomized algorithm that can use the known fast square matrix multiplication algorithms to perform fewer arithmetic operations than the current state of the art for output matrices that are sparse.

In particular, let $\omega$ be the best known constant such that two dense $U \times U$ matrices can be multiplied with $\mathcal{O} \left( U^\omega \right)$ arithmetic operations.

Further denote by $N$ the number of nonzero entries in the input matrices while $Z$ is the number of nonzero entries of matrix product $AC$.

We present a new Monte Carlo algorithm that uses $\tilde{\mathcal{O}} \left( U^2 \left(\frac{Z}{U}\right)^{\omega-2} + N \right)$ arithmetic operations and outputs the nonzero entries of $AC$ with high probability.

For dense input, i.e., $N=U^2$, if $Z$ is asymptotically larger than $U$, this improves over state of the art methods, and it is always at most $\mathcal{O} \left( U^\omega \right)$. For general input density we improve upon state of the art when $N$ is asymptotically larger than $U^{4 - \omega} Z^{\omega - 5/2}$.

The algorithm is based on dividing the input into "balanced" subproblems which are then compressed and computed.

The new subroutine that computes a matrix product with balanced rows and columns in its output uses time $\tilde{\mathcal{O}} \left( U Z^{(\omega -1)/2} + N\right)$ which is better than the current state of the art for balanced matrices when $N$ is asymptotically larger than $U Z^{\omega/2 - 1}$, which always holds when $N=U^2$.

In the I/O model --- where $M$ is the memory size and $B$ is the block size --- our algorithm is the first nontrivial result that exploits cancellations and sparsity of the output. The I/O complexity of our algorithm is $\tilde{\mathcal{O}} \left( U^2 (Z/U)^{\omega-2}/(M^{\omega/2 -1} B) + Z/B + N/B \right)$, which is asymptotically faster than the state of the art unless $M$ is large.

We present a new randomized algorithm that can use the known fast square matrix multiplication algorithms to perform fewer arithmetic operations than the current state of the art for output matrices that are sparse.

In particular, let $\omega$ be the best known constant such that two dense $U \times U$ matrices can be multiplied with $\mathcal{O} \left( U^\omega \right)$ arithmetic operations.

Further denote by $N$ the number of nonzero entries in the input matrices while $Z$ is the number of nonzero entries of matrix product $AC$.

We present a new Monte Carlo algorithm that uses $\tilde{\mathcal{O}} \left( U^2 \left(\frac{Z}{U}\right)^{\omega-2} + N \right)$ arithmetic operations and outputs the nonzero entries of $AC$ with high probability.

For dense input, i.e., $N=U^2$, if $Z$ is asymptotically larger than $U$, this improves over state of the art methods, and it is always at most $\mathcal{O} \left( U^\omega \right)$. For general input density we improve upon state of the art when $N$ is asymptotically larger than $U^{4 - \omega} Z^{\omega - 5/2}$.

The algorithm is based on dividing the input into "balanced" subproblems which are then compressed and computed.

The new subroutine that computes a matrix product with balanced rows and columns in its output uses time $\tilde{\mathcal{O}} \left( U Z^{(\omega -1)/2} + N\right)$ which is better than the current state of the art for balanced matrices when $N$ is asymptotically larger than $U Z^{\omega/2 - 1}$, which always holds when $N=U^2$.

In the I/O model --- where $M$ is the memory size and $B$ is the block size --- our algorithm is the first nontrivial result that exploits cancellations and sparsity of the output. The I/O complexity of our algorithm is $\tilde{\mathcal{O}} \left( U^2 (Z/U)^{\omega-2}/(M^{\omega/2 -1} B) + Z/B + N/B \right)$, which is asymptotically faster than the state of the art unless $M$ is large.

Original language | English |
---|---|

Title of host publication | Algorithms - ESA 2015 : 23rd Annual European Symposium, Patras, Greece, September 14-16, 2015, Proceedings |

Number of pages | 12 |

Publisher | Springer |

Publication date | 14 Sept 2015 |

Pages | 766-778 |

ISBN (Print) | 978-3-662-48349-7 |

ISBN (Electronic) | 978-3-662-48350-3 |

DOIs | |

Publication status | Published - 14 Sept 2015 |

Series | Lecture Notes in Computer Science |
---|---|

Volume | 9294 |

ISSN | 0302-9743 |

## Keywords

- Sparse Matrix Multiplication
- Randomized Algorithms
- Monte Carlo Method
- Arithmetic Operations
- I/O Complexity