Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Fast Boolean matrix multiplication for highly clustered data

Björklund, Andreas LU and Lingas, Andrzej LU (2001) LNCS 2125. p.258-263
Abstract
We consider the problem of computing the product of two

n×n Boolean matrices A and B. For an n×n Boolean matrix C, let GC

be the complete weighted graph on the rows of C where the weight of an

edge between two rows is equal to its Hamming distance, i.e., the number

of entries in the first row having values different from the corresponding

entries in the second one. Next, letMWT(C) be the weight of a minimum

weight spanning tree of GC. We show that the product of A with B as

well as the so called witnesses of the product can be computed in time

(n(n + min{MWT(A),MWT(Bt)}))

˜O
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Algorithms and data structures : 7th International Workshop, WADS 2001, Providence, RI, USA, August 8-10, 2001 : proceedings
volume
LNCS 2125
pages
258 - 263
publisher
Springer
external identifiers
  • scopus:84958053511
ISBN
3540424237
DOI
10.1007/3-540-44634-6_24
language
English
LU publication?
yes
id
62718902-8a17-4700-887a-3cf62f717944 (old id 526578)
date added to LUP
2016-04-04 11:03:39
date last changed
2025-04-04 14:23:28
@inproceedings{62718902-8a17-4700-887a-3cf62f717944,
  abstract     = {{We consider the problem of computing the product of two<br/><br>
n×n Boolean matrices A and B. For an n×n Boolean matrix C, let GC<br/><br>
be the complete weighted graph on the rows of C where the weight of an<br/><br>
edge between two rows is equal to its Hamming distance, i.e., the number<br/><br>
of entries in the first row having values different from the corresponding<br/><br>
entries in the second one. Next, letMWT(C) be the weight of a minimum<br/><br>
weight spanning tree of GC. We show that the product of A with B as<br/><br>
well as the so called witnesses of the product can be computed in time<br/><br>
(n(n + min{MWT(A),MWT(Bt)}))<br/><br>
˜O}},
  author       = {{Björklund, Andreas and Lingas, Andrzej}},
  booktitle    = {{Algorithms and data structures : 7th International Workshop, WADS 2001, Providence, RI, USA, August 8-10, 2001 : proceedings}},
  isbn         = {{3540424237}},
  language     = {{eng}},
  pages        = {{258--263}},
  publisher    = {{Springer}},
  title        = {{Fast Boolean matrix multiplication for highly clustered data}},
  url          = {{https://lup.lub.lu.se/search/files/5685192/623754.pdf}},
  doi          = {{10.1007/3-540-44634-6_24}},
  volume       = {{LNCS 2125}},
  year         = {{2001}},
}