# Lund University Publications

## LUND UNIVERSITY LIBRARIES

### 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)
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
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
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
2016-04-01 11:45:21
date last changed
2021-02-17 04:58:46
```@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},
language     = {eng},
pages        = {501--510},
publisher    = {Springer},
title        = {A geometric approach to Boolean matrix multiplication},