Scholarlink

<p>We study applications of clustering (in particular, the Hamming <i>k</i>-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). 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 <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\({\ell }\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ℓ</mi> </math></EquationSource> </InlineEquation>-center clustering of the rows of the first matrix or an <i>k</i>-center clustering of the columns of the second matrix. 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 alternative 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 <InlineEquation ID="IEq2"> <EquationSource Format="TEX">\({\ell }\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ℓ</mi> </math></EquationSource> </InlineEquation>- and <i>k</i>-center clustering.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Multiplication of 0-1 Matrices via Clustering

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年6月29日

查看全文
  • Jesper Jansson,
  • Miroslaw Kowaluk,
  • Andrzej Lingas,
  • Mia Persson

摘要

We study applications of clustering (in particular, the Hamming 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). 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. 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 alternative 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.