caa a22 4500 445805153 CHVBK 20180317145154.0 cr unu---uuuuu 170323e20110901xx s 000 0 eng 10.1007/s00453-010-9441-x doi (NATIONALLICENCE)springer-10.1007/s00453-010-9441-x Lingas Andrzej Department of Computer Science, Lund University, 22100, Lund, Sweden aut A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication [Elektronische Daten] [Andrzej Lingas] 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 $\widetilde{O}(n^{2}s^{\omega/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 $\widetilde{O}(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 $\widetilde{O}(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 $\widetilde{O}(n^{\omega})$-time algorithm for this problem. By applying the fast rectangular matrix multiplication, we can refine our upper bound further to the form $\widetilde{O}(n^{\omega(\frac{1}{2}\log_{n}s,1,1)})$, where ω(p,q,t) is the exponent of the fast multiplication of an n p×n q matrix by an n q×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. Springer Science+Business Media, LLC, 2010 Boolean matrix multiplication nationallicence Rectangular matrix multiplication nationallicence Output-sensitive algorithm nationallicence Time complexity nationallicence Algorithmica Springer-Verlag 61/1(2011-09-01), 36-50 0178-4617 61:1<36 2011 61 453 https://doi.org/10.1007/s00453-010-9441-x text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/s00453-010-9441-x text/html Onlinezugriff via DOI NATIONALLICENCE 100 1- Lingas Andrzej Department of Computer Science, Lund University, 22100, Lund, Sweden aut NATIONALLICENCE 773 0- Algorithmica Springer-Verlag 61/1(2011-09-01), 36-50 0178-4617 61:1<36 2011 61 453 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer