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

From Algorithm Wiki
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

References/Citation

https://arxiv.org/pdf/1602.06705.pdf