Online Vector-Matrix-Vector Multiplication (Matrix-Vector Multiplication)

From Algorithm Wiki
(Redirected from OuMv)
Jump to navigation Jump to search


Let $M$ be a binary $n \times n$ matrix than can be preprocessed. After preprocessing $n$ vector pairs $(u^1, v^1), \ldots, (u^n, v^n)$, arrive one at a time and the task is to compute $(u^i)^T M v^i$ before being presented with the $i+1$th vector pair for every $i$.

Related Problems

Related: Online Matrix-Vector Multiplication


$n$: dimension of square matrix, number of vector pairs, size of vectors

Table of Algorithms

Currently no algorithms in our database for the given problem.

Reductions TO Problem

Problem Implication Year Citation Reduction
Bipartite Graph MCM assume: OMv
then: there is no algorithm for solving incremental (or decremental) maximum cardinality bipartite matching with amortized time $O(n^{1-\epsilon})$ per insertion (or deletion) and $O(n^{2-\epsilon})$ time per query for any $\epsilon > {0}$
2016 link