Advanced

A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication

Lingas, Andrzej LU (2011) In Algorithmica 61(1). p.36-50
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 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(omega/2-1)), where the input matrices have size nxn, the number of non-zero 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 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(omega/2-1)), where the input matrices have size nxn, the number of non-zero 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 output-sensitive column-row 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 output-sensitive algorithms. (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Boolean matrix multiplication, Rectangular matrix multiplication, Output-sensitive algorithm, Time complexity
in
Algorithmica
volume
61
issue
1
pages
36 - 50
publisher
Springer
external identifiers
  • wos:000291481900003
  • scopus:79959251722
ISSN
0178-4617
DOI
10.1007/s00453-010-9441-x
language
English
LU publication?
yes
id
b75a24ae-6c05-452e-86ef-be533136278c (old id 1985111)
date added to LUP
2011-07-06 15:56:50
date last changed
2017-09-24 03:14:05
@article{b75a24ae-6c05-452e-86ef-be533136278c,
  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 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(omega/2-1)), where the input matrices have size nxn, the number of non-zero 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 output-sensitive column-row 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 output-sensitive algorithms.},
  author       = {Lingas, Andrzej},
  issn         = {0178-4617},
  keyword      = {Boolean matrix multiplication,Rectangular matrix multiplication,Output-sensitive algorithm,Time complexity},
  language     = {eng},
  number       = {1},
  pages        = {36--50},
  publisher    = {Springer},
  series       = {Algorithmica},
  title        = {A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication},
  url          = {http://dx.doi.org/10.1007/s00453-010-9441-x},
  volume       = {61},
  year         = {2011},
}