Fast Boolean matrix multiplication for highly clustered data
Författare
Summary, in English
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
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
Avdelning/ar
- Institutionen för datavetenskap
- Computer Science
- Parallella System
Publiceringsår
2001
Språk
Engelska
Sidor
258-263
Publikation/Tidskrift/Serie
Algorithms and data structures : 7th International Workshop, WADS 2001, Providence, RI, USA, August 8-10, 2001 : proceedings
Volym
LNCS 2125
Fulltext
- Available as PDF - 107 kB
- Download statistics
Dokumenttyp
Konferensbidrag
Förlag
Springer
Ämne
- Computer Science
Status
Published
ISBN/ISSN/Övrigt
- ISBN: 3540424237