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

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

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)

Cites Work

• Introduction to algorithms
• Gaussian elimination is not optimal
• Title not available (Why is that?)
• Matrix multiplication via arithmetic progressions
• General context-free recognition in less than cubic time
• Fast context-free grammar parsing requires fast boolean matrix multiplication
• Fast recognition of pushdown automaton and context-free languages
• Title not available (Why is that?)
• A practical algorithm for Boolean matrix multiplication
• Matrix multiplication for finite algebraic systems

Cited In (1)

• Efficient transitive closure of sparse matrices over closed 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)