Multiplication of 0-1 matrices via clustering
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917172604829696 |
|---|---|
| author | Jansson, Jesper Kowaluk, Miroslaw Lingas, Andrzej Persson, Mia |
| author_facet | Jansson, Jesper Kowaluk, Miroslaw Lingas, Andrzej Persson, Mia |
| contents | We study applications of clustering (in particular, the $k$-center clustering problem) in the design of efficient and practical algorithms for computing an approximate and the exact arithmetic matrix product of two 0-1 rectangular matrices with clustered rows or columns, respectively. Our results in part can be regarded as an extension of the clustering-based approach to Boolean square matrix multiplication due to Arslan and Chidri (CSC 2011). First, we provide a simple and efficient deterministic algorithm for approximate matrix product of 0-1 matrices, where the additive error is proportional to the minimum maximum radius in an $\ell$-center clustering of the rows of the first matrix or an $k$-center clustering of the columns of the second matrix. Next, we use the approximation algorithm as a preprocessing after which a query asking for the exact value of an arbitrary entry in the product matrix can be answered in time proportional to the additive error. As a consequence, we obtain a simple deterministic algorithm for the exact matrix product of 0-1 matrices. We also present an improved simple deterministic algorithm for the exact product and in addition, faster analogous randomized algorithms for an approximate and the exact matrix products of 0-1 matrices based on randomized $\ell$ and $k$-center clustering. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_19631 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Multiplication of 0-1 matrices via clustering Jansson, Jesper Kowaluk, Miroslaw Lingas, Andrzej Persson, Mia Data Structures and Algorithms F.2.2 F.2.2 We study applications of clustering (in particular, the $k$-center clustering problem) in the design of efficient and practical algorithms for computing an approximate and the exact arithmetic matrix product of two 0-1 rectangular matrices with clustered rows or columns, respectively. Our results in part can be regarded as an extension of the clustering-based approach to Boolean square matrix multiplication due to Arslan and Chidri (CSC 2011). First, we provide a simple and efficient deterministic algorithm for approximate matrix product of 0-1 matrices, where the additive error is proportional to the minimum maximum radius in an $\ell$-center clustering of the rows of the first matrix or an $k$-center clustering of the columns of the second matrix. Next, we use the approximation algorithm as a preprocessing after which a query asking for the exact value of an arbitrary entry in the product matrix can be answered in time proportional to the additive error. As a consequence, we obtain a simple deterministic algorithm for the exact matrix product of 0-1 matrices. We also present an improved simple deterministic algorithm for the exact product and in addition, faster analogous randomized algorithms for an approximate and the exact matrix products of 0-1 matrices based on randomized $\ell$ and $k$-center clustering. |
| title | Multiplication of 0-1 matrices via clustering |
| topic | Data Structures and Algorithms F.2.2 F.2.2 |
| url | https://arxiv.org/abs/2503.19631 |