Special matrices for which the cost of matrix-vector multiplication is less than $O(n^2)$ I am looking for some special type of matrices for which the cost of matrix-vector multiplication is less than $O(n^2)$. Examples are Hankel and Toeplitz matrices, which have few degrees of freedom (i.e., less than the number of free variables). Is there some other kind of matrix that has more degrees of freedom?
 A: If you a sparse matrix by which, I mean sparse in conventional sense with zero fill-ins, then the cost is obviously less than $\mathcal{O}(n^2)$. For instance, banded matrices can be multiplied with a vector in $\mathcal{O}(bn)$, where $b$ is the band-width of the matrix.
There are also dense matrices, which are sparse in the sense of data sparsity. For instance, the Topelitz and Hankel matrices have information content of $\mathcal{O}(n)$. For these matrices, the matrix-vector product can be done in almost linear complexity i.e. $\mathcal{O}(n \log^{\alpha} n)$, where $\alpha \in \{0,1\}$.
Apart from these conventional structures, if we have a low-rank matrix say of rank $r \ll n$, where $n$ is the size of the matrix, and know that it is low-rank of rank $r$, factor it using fast low-rank factorizations ($\mathcal{O}(n)$) like rank reduced LU or rank reduced QR or other interpolation techniques to get it into a factored form and perform matrix vector products in $\mathcal{O}(rn)$ complexity.

Using this idea, there is a class of matrices known as hierarchical matrices ($\mathcal{H}$,$\mathcal{H}^2$, HODLR, p-HSS, HSS matrices) for which matrix-vector products can be obtained in $\mathcal{O}(n \log^{\beta})$ complexity, where $\beta \in \{0,1\}$. For these hierarchical matrices, the low-rank blocks arise in a recursive fashion, where in certain sub blocks of the matrices at each level in the recursion are low-rank.

Most of the dense matrices arising in engineering applications like for instance matrices arising out of $N$ body problems in computational physics, boundary element method, covariance matrices, Jacobian matrices, etc., can be well modelled/ approximated using these hierarchical matrices. If you are familiar with fast multipole method, these hierarchical matrices are nothing but a algebraic generalization of the matrices arising in fast multipole method. Further, there are different hierarchical structures one could exploit. The structure I have shown above is for $\mathcal{H}$ or $\mathcal{H}^2$-matrices. Another popular hierarchical structure is the hierarchical semi-separable structure (HSS), where the off-diagonal blocks are low-rank and these low-rank have a nested basis.
Another powerful application of these matrices is that we can even construct direct linear solvers in almost linear complexity i.e. $\mathcal{O}(r^2 n \log^{\alpha} n)$, where $\alpha \in \{0,1,2\}$.
