Advanced

A fast output-sensitive algorithm for Boolean matrix multiplication

Lingas, Andrzej LU (2009) 17th Annual European Symposium on Algorithms In Algorithms - ESA 2009, Proceedings 5757. p.408-419
Abstract
We use randomness to exploit the potential sparsity of the Boolean matrix product in order to speed up the computation of the product. Our new fast output-sensitive algorithm for Boolean matrix product and its witnesses is randomized and provides the Boolean product and its witnesses almost certainly. Its worst-case time performance is expressed in terms of the input size and the number of non-zero entries of the product matrix. It runs in time (O) over tilde (n(2)s(w/2-1)), where the input matrices have size n, X 11,, the number of non-zero entries in the product matrix is at most.s, w is the exponent of the fast matrix multiplication and 0( f (n,)) denotes 0(f) logd 71) for some constant d. By the currently best bound on w, its running... (More)
We use randomness to exploit the potential sparsity of the Boolean matrix product in order to speed up the computation of the product. Our new fast output-sensitive algorithm for Boolean matrix product and its witnesses is randomized and provides the Boolean product and its witnesses almost certainly. Its worst-case time performance is expressed in terms of the input size and the number of non-zero entries of the product matrix. It runs in time (O) over tilde (n(2)s(w/2-1)), where the input matrices have size n, X 11,, the number of non-zero entries in the product matrix is at most.s, w is the exponent of the fast matrix multiplication and 0( f (n,)) denotes 0(f) logd 71) for some constant d. By the currently best bound on w, its running time can be also expressed as 0(712s0"188). Our algorithm is substantially faster than the output-sensitive column-row method for Boolean matrix product for s larger than n1.232 and it is never slower than the fast 0(r')time algorithm for this problem. We also present a partial derandomization of our algorithm as well as its generalization to include the Boolean product of rectangular Boolean matrices. Finally, we show several applications of our output-sensitive algorithms. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
in
Algorithms - ESA 2009, Proceedings
volume
5757
pages
408 - 419
publisher
Springer
conference name
17th Annual European Symposium on Algorithms
external identifiers
  • wos:000279102100037
  • scopus:70350749134
ISSN
0302-9743
1611-3349
DOI
10.1007/978-3-642-04128-0_37
project
VR 2008-4649
language
English
LU publication?
yes
id
b052250c-c85e-4425-9227-c42a6011a99f (old id 1628610)
date added to LUP
2010-07-23 09:54:40
date last changed
2017-06-04 03:33:07
@inproceedings{b052250c-c85e-4425-9227-c42a6011a99f,
  abstract     = {We use randomness to exploit the potential sparsity of the Boolean matrix product in order to speed up the computation of the product. Our new fast output-sensitive algorithm for Boolean matrix product and its witnesses is randomized and provides the Boolean product and its witnesses almost certainly. Its worst-case time performance is expressed in terms of the input size and the number of non-zero entries of the product matrix. It runs in time (O) over tilde (n(2)s(w/2-1)), where the input matrices have size n, X 11,, the number of non-zero entries in the product matrix is at most.s, w is the exponent of the fast matrix multiplication and 0( f (n,)) denotes 0(f) logd 71) for some constant d. By the currently best bound on w, its running time can be also expressed as 0(712s0"188). Our algorithm is substantially faster than the output-sensitive column-row method for Boolean matrix product for s larger than n1.232 and it is never slower than the fast 0(r')time algorithm for this problem. We also present a partial derandomization of our algorithm as well as its generalization to include the Boolean product of rectangular Boolean matrices. Finally, we show several applications of our output-sensitive algorithms.},
  author       = {Lingas, Andrzej},
  booktitle    = {Algorithms - ESA 2009, Proceedings},
  issn         = {0302-9743},
  language     = {eng},
  pages        = {408--419},
  publisher    = {Springer},
  title        = {A fast output-sensitive algorithm for Boolean matrix multiplication},
  url          = {http://dx.doi.org/10.1007/978-3-642-04128-0_37},
  volume       = {5757},
  year         = {2009},
}