A Two Pronged Progress in Structured Dense Matrix Multiplication

Understand

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 $\Theta(N^2)$ operations over $\mathbb{F}$ are needed to compute $Ab$.
• A broad question is to identify classes of structured dense matrices that can be represented with $O(N)$ parameters, and for which matrix-vector multiplication can be performed sub-quadratically.
• One such class of structured matrices is the orthogonal polynomial transforms, whose rows correspond to a family of orthogonal polynomials.