Matrix-vector multiplication in sub-quadratic time (some preprocessing required)

MaRDI QIDQ2934692zbMATH OpenFDO

Authors Ryan Williams

Publication date 18 December 2014

Mathematics Subject Classification ID

Complexity and performance of numerical algorithms (65Y20) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Fast algorithms with preprocessing for matrix-vector multiplication problems
• An optimal algorithm for matrix multiplication
• Faster Online Matrix-Vector Multiplication
• The Mailman algorithm: a note on matrix-vector multiplication
• Fast rectangular matrix multiplication and applications

Cited in

(14)

• Fast algorithms with preprocessing for matrix-vector multiplication problems
• Improved normal form for grammars with one-sided contexts
• Logic minimization techniques with applications to cryptology
• Orthogonal range searching in moderate dimensions: k-d trees and range trees strike back
• Pushing the online Boolean matrix-vector multiplication conjecture off-line and identifying its easy cases
• Faster algorithms for weighted recursive state machines
• Edit distance with duplications and contractions revisited
• scientific article; zbMATH DE number 3940617 (Why is no real title available?)
• Parsing by matrix multiplication generalized to Boolean grammars
• Sketching with Kerdock's crayons: fast sparsifying transforms for arbitrary linear maps
• A sparsified Four-Russian algorithm for RNA folding
• On the complexity of algorithms with predictions for dynamic graph problems
• Finding Nash equilibrium in bimatrix games in zero-error probabilistic polynomial time
• The Mailman algorithm: a note on matrix-vector multiplication

This page was built for publication: Matrix-vector multiplication in sub-quadratic time (some preprocessing required)

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