Online Vector-Matrix-Vector Multiplication (Matrix-Vector Multiplication)
Jump to navigation
Jump to search
Description
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
Parameters
$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 | https://arxiv.org/abs/1602.06705 | link |