An improved algorithm for Boolean matrix multiplication (Q1068514): Difference between revisions
From MaRDI portal
Removed claim: author (P16): Item:Q170450 |
Set OpenAlex properties. |
||
(3 intermediate revisions by 3 users not shown) | |||
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 | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1007/bf02240211 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W184459568 / rank | |||
Normal rank |
Latest revision as of 09:37, 30 July 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