A Fast OutputSensitive Algorithm for Boolean Matrix Multiplication
(2011) In Algorithmica 61(1). p.3650 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(omega/21)), where the input matrices have size nxn, the number of nonzero entries in the product matrix is at most s, omega is the exponent of the fast matrix multiplication and (O) over tilde (f(n)) denotes O(f(n)log(d) n) for some constant d. By the currently best bound on.,... (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(omega/21)), where the input matrices have size nxn, the number of nonzero entries in the product matrix is at most s, omega is the exponent of the fast matrix multiplication and (O) over tilde (f(n)) denotes O(f(n)log(d) n) for some constant d. By the currently best bound on., its running time can be also expressed as (O) over tilde (n(2)s(0.188)). Our algorithm is substantially faster than the outputsensitive columnrow method for Boolean matrix product for s larger than n(1.232) and it is never slower than the fast (O) over tilde (n(omega))time algorithm for this problem. By applying the fast rectangular matrix multiplication, we can refine our upper bound further to the form (O) over tilde (n(omega(1/2) (logns, 1,1))), where omega(p, q, t) is the exponent of the fast multiplication of an n(p) x n(q) matrix by an n(q) x n(t) matrix. 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/1985111
 author
 Lingas, Andrzej ^{LU}
 organization
 publishing date
 2011
 type
 Contribution to journal
 publication status
 published
 subject
 keywords
 Boolean matrix multiplication, Rectangular matrix multiplication, Outputsensitive algorithm, Time complexity
 in
 Algorithmica
 volume
 61
 issue
 1
 pages
 36  50
 publisher
 Springer
 external identifiers

 wos:000291481900003
 scopus:79959251722
 ISSN
 01784617
 DOI
 10.1007/s004530109441x
 language
 English
 LU publication?
 yes
 id
 b75a24ae6c05452e86efbe533136278c (old id 1985111)
 date added to LUP
 20110706 15:56:50
 date last changed
 20170924 03:14:05
@article{b75a24ae6c05452e86efbe533136278c, 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(omega/21)), where the input matrices have size nxn, the number of nonzero entries in the product matrix is at most s, omega is the exponent of the fast matrix multiplication and (O) over tilde (f(n)) denotes O(f(n)log(d) n) for some constant d. By the currently best bound on., its running time can be also expressed as (O) over tilde (n(2)s(0.188)). Our algorithm is substantially faster than the outputsensitive columnrow method for Boolean matrix product for s larger than n(1.232) and it is never slower than the fast (O) over tilde (n(omega))time algorithm for this problem. By applying the fast rectangular matrix multiplication, we can refine our upper bound further to the form (O) over tilde (n(omega(1/2) (logns, 1,1))), where omega(p, q, t) is the exponent of the fast multiplication of an n(p) x n(q) matrix by an n(q) x n(t) matrix. 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}, issn = {01784617}, keyword = {Boolean matrix multiplication,Rectangular matrix multiplication,Outputsensitive algorithm,Time complexity}, language = {eng}, number = {1}, pages = {3650}, publisher = {Springer}, series = {Algorithmica}, title = {A Fast OutputSensitive Algorithm for Boolean Matrix Multiplication}, url = {http://dx.doi.org/10.1007/s004530109441x}, volume = {61}, year = {2011}, }