Online Vector-Matrix-Vector Multiplication: Difference between revisions
Jump to navigation
Jump to search
(Created page with "{{DISPLAYTITLE:Online Vector-Matrix-Vector Multiplication (Matrix-Vector Multiplication)}} == 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 == <...") |
No edit summary |
||
| (One intermediate revision by the same user not shown) | |||
| Line 10: | Line 10: | ||
== Parameters == | == Parameters == | ||
$n$: dimension of square matrix, number of vector pairs, size of vectors | |||
== Table of Algorithms == | == Table of Algorithms == | ||
Latest revision as of 08:28, 10 April 2023
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 |