Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

A geometric approach to Boolean matrix multiplication

Författare

Summary, in English

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.

Avdelning/ar

  • Computer Science

Publiceringsår

2002

Språk

Engelska

Sidor

501-510

Publikation/Tidskrift/Serie

Algorithms and Computation : 13th International Symposium, ISAAC 2002, Vancouver, BC, Canada, November 21-23, 2002. Proceedings (Lecture Notes in Computer Science)

Volym

2518

Dokumenttyp

Konferensbidrag

Förlag

Springer

Ämne

  • Computer Science

Nyckelord

  • 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

Conference name

Algorithms and Computation. 13th International Symposium, ISSAC 2002.

Conference date

2002-11-21 - 2002-11-23

Conference place

Vancouver, BC, Canada

Status

Published

ISBN/ISSN/Övrigt

  • ISSN: 1611-3349
  • ISSN: 0302-9743