Atri Rudra

A Two Pronged Progress in Structured Dense Matrix Multiplication

2016 · arXiv (Cornell University)

Matrix-vector multiplication is one of the most fundamental computing primitives. Given a matrix $A\in\mathbb{F}^{N\times N}$ and a vector $b$, it is known that in the worst case $Θ(N^2)$ operations over $\mathbb{F}$ are needed to compute …