Fast multiplication of matrices over a finitely generated semiring

DOI10.1016/J.IPL.2008.03.004zbMATH Open1189.65074OpenAlexW2047445951MaRDI QIDQ963453FDOQ963453

Authors Daniel Andrén, Lars Hellström, Klas Markström

Publication date 19 April 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2008.03.004

zbMATH Keywords

complexitymatrix multiplicationsemiringsBoolean matrix multiplicationcombinatorial matrix multiplication algorithm

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Matrices over special rings (quaternions, finite fields, etc.) (15B33) Semirings (16Y60)

Recommendations

• Algorithms – ESA 2004
• Fast sparse matrix multiplication
• Matrix multiplication for finite algebraic systems
• Matrix multiplication via arithmetic progressions
• On practical algorithms for accelerated matrix multiplication

Cites work

• scientific article; zbMATH DE number 976329 (Why is no real title available?)
• scientific article; zbMATH DE number 3340123 (Why is no real title available?)
• A practical algorithm for Boolean matrix multiplication
• Fast context-free grammar parsing requires fast Boolean matrix multiplication
• Fast recognition of pushdown automaton and context-free languages
• Gaussian elimination is not optimal
• General context-free recognition in less than cubic time
• Introduction to algorithms
• Matrix multiplication for finite algebraic systems
• Matrix multiplication via arithmetic progressions

Cited in

(2)

• Efficient transitive closure of sparse matrices over closed semirings
• Quantum algorithms for matrix products over semirings

This page was built for publication: Fast multiplication of matrices over a finitely generated semiring

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