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(n~2s~(ω/2-1)), where the input matrices have size n × n, the number of non-zero entries in the product matrix is at most s, ω is the exponent of the fast matrix multiplication and O(f(n)) denotes O(f(n) log~d n) for some constant d. By the currently best bound on uj, its running time can be also expressed as O(n~2s~(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(n~ω)-time algorithm for this problem.rnWe 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.
展开▼
