# Special Matrices which have matrix-vector multiplication complexity less than $O(n^2)$

I am looking for some special type of matrices, such that the matrix vector multiplication complexity is less than $O(n^2)$. A few such examples are Hankel and Toeplitz. But they have very less degrees of freedom (i.e. less number of free variables). Can I have some other kind of matrix that has somewhat more degree of freedoms.

-
The complexity of multiplication would be bounded below by the degrees of freedom. I guess you can have some other kinds of matrices with more degrees of freedom. – Tunococ Jan 19 '13 at 1:44
Any matrix with $o(n^2)$ non-zero entries would be an example. – Tunococ Jan 19 '13 at 1:49
Agree with @Tunococ, with the caveat that you're using a sparse representation of the matrix family. – John Moeller Jan 19 '13 at 3:40
Hadamard matrices? Discrete Fourier Transform matrixes (especially when $n$ is a highly composite integer)? – Dilip Sarwate Jan 19 '13 at 3:51

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\}$.

-
Thanks for the reply. This helps a lot – user58837 Jan 21 '13 at 22:08