An improved algorithm for Boolean matrix multiplication

DOI10.1007/BF02240211MaRDI QIDQ1068514zbMATH OpenOpenAlexFDO

Authors N. Santoro, J. Urrutia

Publication date 1986

Published in Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02240211

zbMATH Keywords

analysis of algorithmsBoolean matrix multiplicationFour Russians' method

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Review text

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.

Recommendations

• A new algorithm for Boolean matrix multiplication
• Speeding up the four Russians algorithm by about one more logarithmic factor
• A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication
• A fast output-sensitive algorithm for Boolean matrix multiplication
• Fast practical algorithms for the Boolean-product-witness-matrix problem

Cites work

• A note on Boolean matrix multiplication

Cited in

(16)

• An efficient algorithm for calculating Boolean difference
• A practical algorithm for Boolean matrix multiplication
• Design of cellular manufacturing systems based on asymptotic forms of a Boolean matrix
• On the use of the asymptotic forms of the Boolean matrix for designing cellular manufacturing systems. -- An improved approach
• Lower bounds for combinatorial algorithms for Boolean matrix multiplication
• A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication
• scientific article; zbMATH DE number 3917556 (Why is no real title available?)
• scientific article; zbMATH DE number 1979525 (Why is no real title available?)
• On minimum witnesses for Boolean matrix multiplication
• A new algorithm for Boolean matrix multiplication
• Speeding up the four Russians algorithm by about one more logarithmic factor
• A Fast Algorithm to Calculate Powers of a Boolean Matrix for Diameter Computation of Random Graphs
• A fast output-sensitive algorithm for Boolean matrix multiplication
• A note on Boolean matrix multiplication
• Bit complexity of matrix products
• The Mailman algorithm: a note on matrix-vector multiplication

This page was built for publication: An improved algorithm for Boolean matrix multiplication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1068514)