A fast outputsensitive algorithm for Boolean matrix multiplication
(2009) 17th Annual European Symposium on Algorithms In Algorithms  ESA 2009, Proceedings 5757. p.408419 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 outputsensitive algorithm for Boolean matrix product and its witnesses is randomized and provides the Boolean product and its witnesses almost certainly. Its worstcase time performance is expressed in terms of the input size and the number of nonzero entries of the product matrix. It runs in time (O) over tilde (n(2)s(w/21)), where the input matrices have size n, X 11,, the number of nonzero 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 outputsensitive algorithm for Boolean matrix product and its witnesses is randomized and provides the Boolean product and its witnesses almost certainly. Its worstcase time performance is expressed in terms of the input size and the number of nonzero entries of the product matrix. It runs in time (O) over tilde (n(2)s(w/21)), where the input matrices have size n, X 11,, the number of nonzero 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 outputsensitive columnrow 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 outputsensitive algorithms. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/1628610
 author
 Lingas, Andrzej ^{LU}
 organization
 publishing date
 2009
 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
 03029743
 16113349
 DOI
 10.1007/9783642041280_37
 project
 VR 20084649
 language
 English
 LU publication?
 yes
 id
 b052250cc85e44259227c42a6011a99f (old id 1628610)
 date added to LUP
 20100723 09:54:40
 date last changed
 20170604 03:33:07
@inproceedings{b052250cc85e44259227c42a6011a99f, 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 outputsensitive algorithm for Boolean matrix product and its witnesses is randomized and provides the Boolean product and its witnesses almost certainly. Its worstcase time performance is expressed in terms of the input size and the number of nonzero entries of the product matrix. It runs in time (O) over tilde (n(2)s(w/21)), where the input matrices have size n, X 11,, the number of nonzero 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 outputsensitive columnrow 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 outputsensitive algorithms.}, author = {Lingas, Andrzej}, booktitle = {Algorithms  ESA 2009, Proceedings}, issn = {03029743}, language = {eng}, pages = {408419}, publisher = {Springer}, title = {A fast outputsensitive algorithm for Boolean matrix multiplication}, url = {http://dx.doi.org/10.1007/9783642041280_37}, volume = {5757}, year = {2009}, }