Fast Output-Sensitive Matrix Multiplication

DOI10.1007/978-3-662-48350-3_64MaRDI QIDQ3452839zbMATH OpenOpenAlexFDO

Authors Riko Jacob, Morten Stöckel

Publication date 19 November 2015

Published in Algorithms - ESA 2015 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-662-48350-3_64

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Randomized algorithms (68W20) Analysis of algorithms (68W40)

Recommendations

• A fast output-sensitive algorithm for Boolean matrix multiplication
• A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication
• Fast hybrid matrix multiplication algorithms
• Algorithms – ESA 2004
• Fast sparse matrix multiplication
• Fast rectangular matrix multiplication and applications
• A practical algorithm for faster matrix multiplication
• Fast interval matrix multiplication
• On practical algorithms for accelerated matrix multiplication
• Fast matrix multiplication using coherent configurations

Cites work

• A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication
• A note on compressed sensing and the complexity of matrix multiplication
• Color-coding
• Compressed matrix multiplication
• Concentration of Measure for the Analysis of Randomized Algorithms
• Fast sparse matrix multiplication
• Finding and counting given length cycles
• Gaussian elimination is not optimal
• Matching is as easy as matrix inversion
• Matrix multiplication via arithmetic progressions
• Maximum matchings in general graphs through randomization
• Multiplying matrices faster than coppersmith-winograd
• Speeding up the four Russians algorithm by about one more logarithmic factor
• The input/output complexity of sparse matrix multiplication

Cited in

(16)

• Compressed matrix multiplication
• Algorithms – ESA 2004
• A note on compressed sensing and the complexity of matrix multiplication
• An introduction to the computational complexity of matrix multiplication
• Improving compressed matrix multiplication using control variate method
• Fast matrix multiplication is stable
• On nondeterministic derandomization of Freivalds' algorithm: consequences, avenues and algorithmic progress
• Efficient complex matrix multiplication
• Evaluating non-square sparse bilinear forms on multiple vector pairs in the I/O-model
• Optimal sparse matrix dense vector multiplication in the I/O-model
• Faster Online Matrix-Vector Multiplication
• Average-case complexity of the min-sum matrix product problem
• A fast output-sensitive algorithm for Boolean matrix multiplication
• Fast matrix multiplication using coherent configurations
• Algorithm design for tensor units
• The input/output complexity of sparse matrix multiplication

This page was built for publication: Fast Output-Sensitive Matrix Multiplication

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