An improved algorithm for Boolean matrix multiplication (Q1068514): Difference between revisions
From MaRDI portal
ReferenceBot (talk | contribs) Changed an Item |
Set OpenAlex properties. |
||
| 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 08: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
