An improved algorithm for Boolean matrix multiplication (Q1068514): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
| (4 intermediate revisions by 3 users not shown) | |||
| Property / author | |||
| Property / author: Jorge Urrutia / rank | |||
| Property / author | |||
| Property / author: Jorge Urrutia / rank | |||
Normal rank | |||
| 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 | |||
| links / mardi / name | links / mardi / name | ||
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
