Abstract
We consider the problem of doing fast and reliable estimation of the number z of non-zero entries in a sparse boolean matrix product. This problem has applications in databases and computer algebra. Finally, we present experiments on real-world data sets that show the accuracy of both our methods to be significantly better than the worstcase analysis predicts.
| Original language | English |
|---|---|
| Journal | Algorithmica |
| Volume | 69 |
| Issue number | 3 |
| Pages (from-to) | 741-757 |
| ISSN | 0178-4617 |
| Publication status | Published - Jul 2013 |
Keywords
- Algorithms
- Matrix multiplication
- Relational algebra
- Theory