A Geometric Approach to Boolean Matrix Multiplication

摘要

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 * n Boolean matrices A and B totally with q edges are given. We show that in time O-tilde(q + min{r_Ar_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 O(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-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-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.