A geometric approach to Boolean matrix multiplication
(2002) Algorithms and Computation. 13th International Symposium, ISSAC 2002. 2518. p.501-510- 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 1-entries in D. Next, let m(D) be the minimum of the number of 0-entries and the number of 1-entries in D. Suppose that the rectilinear regions formed by the 1-entries 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 1-entries in D. Next, let m(D) be the minimum of the number of 0-entries and the number of 1-entries in D. Suppose that the rectilinear regions formed by the 1-entries 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 sub-cubic algorithms for Boolean matrix multiplication based on arithmetic 0 - 1-matrix 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:
https://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
- sweep-line 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
- host publication
- Algorithms and Computation : 13th International Symposium, ISAAC 2002, Vancouver, BC, Canada, November 21-23, 2002. Proceedings (Lecture Notes in Computer Science)
- volume
- 2518
- pages
- 501 - 510
- publisher
- Springer
- conference name
- Algorithms and Computation. 13th International Symposium, ISSAC 2002.
- conference location
- Vancouver, BC, Canada
- conference dates
- 2002-11-21 - 2002-11-23
- external identifiers
-
- wos:000182826400044
- scopus:84878624706
- ISSN
- 1611-3349
- 0302-9743
- language
- English
- LU publication?
- yes
- id
- 2f32c049-295f-4de2-b1dc-20685a70b30d (old id 311046)
- alternative location
- http://www.springerlink.com/content/f05vxkkw7ryq7fjp
- date added to LUP
- 2016-04-01 11:45:21
- date last changed
- 2024-01-22 17:06:22
@inproceedings{2f32c049-295f-4de2-b1dc-20685a70b30d,
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 1-entries in D. Next, let m(D) be the minimum of the number of 0-entries and the number of 1-entries in D. Suppose that the rectilinear regions formed by the 1-entries 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 sub-cubic algorithms for Boolean matrix multiplication based on arithmetic 0 - 1-matrix 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 21-23, 2002. Proceedings (Lecture Notes in Computer Science)}},
issn = {{1611-3349}},
keywords = {{sweep-line 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 = {{501--510}},
publisher = {{Springer}},
title = {{A geometric approach to Boolean matrix multiplication}},
url = {{http://www.springerlink.com/content/f05vxkkw7ryq7fjp}},
volume = {{2518}},
year = {{2002}},
}