A geometric approach to Boolean matrix multiplication
(2002) Algorithms and Computation. 13th International Symposium, ISSAC 2002. In Algorithms and Computation : 13th International Symposium, ISAAC 2002, Vancouver, BC, Canada, November 2123, 2002. Proceedings (Lecture Notes in Computer Science) 2518. p.501510 Abstract
 For a Boolean matrix D, let r(D) be the minimum number of rectangles sufficient to cover exactly the rectilinear region formed by the 1entries in D. Next, let m(D) be the minimum of the number of 0entries and the number of 1entries in D. Suppose that the rectilinear regions formed by the 1entries in two n x n Boolean matrices A and B totally with q edges are given. We show that in time (O) over tilde (q + min{r(A)r(B), n(n + r(A)), n(n + r(B))})(1) one can construct a data structure which for any entry of the Boolean product of A and B reports whether or not it is equal to 1, and if so, reports also the so called witness of the entry, in time 0 (log q). As a corollary, we infer that if the matrices A and B are given as input, their... (More)
 For a Boolean matrix D, let r(D) be the minimum number of rectangles sufficient to cover exactly the rectilinear region formed by the 1entries in D. Next, let m(D) be the minimum of the number of 0entries and the number of 1entries in D. Suppose that the rectilinear regions formed by the 1entries in two n x n Boolean matrices A and B totally with q edges are given. We show that in time (O) over tilde (q + min{r(A)r(B), n(n + r(A)), n(n + r(B))})(1) one can construct a data structure which for any entry of the Boolean product of A and B reports whether or not it is equal to 1, and if so, reports also the so called witness of the entry, in time 0 (log q). As a corollary, we infer that if the matrices A and B are given as input, their product and the witnesses of the product can be computed in time (O) over tilde (n(n + min{r(A), r(B)})). This implies in particular that the product of A and B and its witnesses can be computed in time (O) over tilde (n(n + min{m(A),m(B)})). In contrast to the known subcubic algorithms for Boolean matrix multiplication based on arithmetic 0  1matrix multiplication, our algorithms do not involve large hidden constants in their running time and are easy to implement. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/311046
 author
 Lingas, Andrzej ^{LU}
 organization
 publishing date
 2002
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 keywords
 sweepline method, running time, asymptotic upper bounds, spanning tree, time probability, monotone circuits, combinatorial algorithm, subcubic approximation, hidden constants, arithmetic (0  1)matrix multiplication, subcubic algorithms, input matrices, entry witness, Boolean product, data structure, Boolean matrices, rectilinear region, rectangles, minimum number, geometric approach, Boolean matrix multiplication
 in
 Algorithms and Computation : 13th International Symposium, ISAAC 2002, Vancouver, BC, Canada, November 2123, 2002. Proceedings (Lecture Notes in Computer Science)
 volume
 2518
 pages
 501  510
 publisher
 Springer
 conference name
 Algorithms and Computation. 13th International Symposium, ISSAC 2002.
 external identifiers

 wos:000182826400044
 scopus:84878624706
 ISSN
 03029743
 16113349
 language
 English
 LU publication?
 yes
 id
 2f32c049295f4de2b1dc20685a70b30d (old id 311046)
 alternative location
 http://www.springerlink.com/content/f05vxkkw7ryq7fjp
 date added to LUP
 20071128 10:00:22
 date last changed
 20170326 03:28:30
@inproceedings{2f32c049295f4de2b1dc20685a70b30d, abstract = {For a Boolean matrix D, let r(D) be the minimum number of rectangles sufficient to cover exactly the rectilinear region formed by the 1entries in D. Next, let m(D) be the minimum of the number of 0entries and the number of 1entries in D. Suppose that the rectilinear regions formed by the 1entries in two n x n Boolean matrices A and B totally with q edges are given. We show that in time (O) over tilde (q + min{r(A)r(B), n(n + r(A)), n(n + r(B))})(1) one can construct a data structure which for any entry of the Boolean product of A and B reports whether or not it is equal to 1, and if so, reports also the so called witness of the entry, in time 0 (log q). As a corollary, we infer that if the matrices A and B are given as input, their product and the witnesses of the product can be computed in time (O) over tilde (n(n + min{r(A), r(B)})). This implies in particular that the product of A and B and its witnesses can be computed in time (O) over tilde (n(n + min{m(A),m(B)})). In contrast to the known subcubic algorithms for Boolean matrix multiplication based on arithmetic 0  1matrix multiplication, our algorithms do not involve large hidden constants in their running time and are easy to implement.}, author = {Lingas, Andrzej}, booktitle = {Algorithms and Computation : 13th International Symposium, ISAAC 2002, Vancouver, BC, Canada, November 2123, 2002. Proceedings (Lecture Notes in Computer Science)}, issn = {03029743}, keyword = {sweepline method,running time,asymptotic upper bounds,spanning tree,time probability,monotone circuits,combinatorial algorithm,subcubic approximation,hidden constants,arithmetic (0  1)matrix multiplication,subcubic algorithms,input matrices,entry witness,Boolean product,data structure,Boolean matrices,rectilinear region,rectangles,minimum number,geometric approach,Boolean matrix multiplication}, language = {eng}, pages = {501510}, publisher = {Springer}, title = {A geometric approach to Boolean matrix multiplication}, volume = {2518}, year = {2002}, }