Carleton University
Technical Report TR-38
January 1984
An Improved Algorithm for Boolean Matrix Multiplication
N. Santoro & J. Urrutia
Abstract
In parallel with the analysis of asymptotically fast methods, the research on Boolean matrix multiplication has also focused on the determination of ‘efficient’ bounds; that is, finding non-optimal but practical algorithms that outperform the asymptotic algorithms for a bounded matrix size or for special classes of matrices. Example of these results are the O(N2) algorithms for multiplying N x N sparse or dense Boolean matrices [2], and the o(N3/log N) algorithm for multiplying arbitrary N x N Boolean matrices [1 ]. The latter algorithm, known as the “Four Russians’ Method”, unfortunately requires O(N3/log N) additional bits to store the O(N/log N) sets, each containing N rows of N bits each.