An improved algorithm for Boolean matrix multiplication (Q1068514): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
| Property / MaRDI profile type | |||
| Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Revision as of 03:04, 5 March 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
