Advanced

A geometric approach to Boolean matrix multiplication

Lingas, Andrzej LU (2002) Algorithms and Computation. 13th International Symposium, ISSAC 2002. In Algorithms and Computation : 13th International Symposium, ISAAC 2002, Vancouver, BC, Canada, November 21-23, 2002. Proceedings (Lecture Notes in Computer Science) 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:
author
organization
publishing date
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
in
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.
external identifiers
  • wos:000182826400044
  • scopus:84878624706
ISSN
0302-9743
1611-3349
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
2007-11-28 10:00:22
date last changed
2017-03-26 03:28:30
@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         = {0302-9743},
  keyword      = {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},
  volume       = {2518},
  year         = {2002},
}