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

(12)

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

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)