Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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.

enter image description here

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.

enter image description here

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

share|cite|improve this answer
Thanks for the reply. This helps a lot – user58837 Jan 21 '13 at 22:08

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.