A geometric approach to Boolean matrix multiplication

    Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceedingResearchpeer-review

    5 Citations (SciVal)

    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.
    Original languageEnglish
    Title of host publicationAlgorithms and Computation : 13th International Symposium, ISAAC 2002, Vancouver, BC, Canada, November 21-23, 2002. Proceedings (Lecture Notes in Computer Science)
    PublisherSpringer
    Pages501-510
    Volume2518
    Publication statusPublished - 2002
    EventAlgorithms and Computation. 13th International Symposium, ISSAC 2002. - Vancouver, BC, Canada
    Duration: 2002 Nov 212002 Nov 23

    Publication series

    Name
    Volume2518
    ISSN (Print)0302-9743
    ISSN (Electronic)1611-3349

    Conference

    ConferenceAlgorithms and Computation. 13th International Symposium, ISSAC 2002.
    Country/TerritoryCanada
    CityVancouver, BC
    Period2002/11/212002/11/23

    Subject classification (UKÄ)

    • Computer Science

    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

    Fingerprint

    Dive into the research topics of 'A geometric approach to Boolean matrix multiplication'. Together they form a unique fingerprint.

    Cite this