An improved algorithm for Boolean matrix multiplication (Q1068514): Difference between revisions
From MaRDI portal
Changed an Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(One intermediate revision by one other user not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A note on Boolean matrix multiplication / rank | |||
Normal rank |
Latest revision as of 10:23, 17 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An improved algorithm for Boolean matrix multiplication |
scientific article |
Statements
An improved algorithm for Boolean matrix multiplication (English)
0 references
1986
0 references
A new algorithm for computing the product of two arbitrary \(N\times N\) Boolean matrices is presented. The algorithm requires \(O(N^ 3/\log N)\) bit operations and only O(N log N) bits of additional storage. This represents an improvement on the Four Russians' method which requires the same number of operations but uses \(O(N^ 3/\log N)\) bits of additional storage.
0 references
Boolean matrix multiplication
0 references
analysis of algorithms
0 references
Four Russians' method
0 references