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

zbMATH Open1302.65111MaRDI QIDQ2934692FDOQ2934692

Authors: Ryan Williams 

Publication date: 18 December 2014

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

Mathematics Subject Classification ID

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

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
• Title not available (Why is that?)
• A sparsified Four-Russian algorithm for RNA folding
• Faster algorithms for weighted recursive state machines
• The Mailman algorithm: a note on matrix-vector multiplication
• 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
• Edit distance with duplications and contractions revisited
• Parsing by matrix multiplication generalized to Boolean grammars

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)