MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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


For an $n \times n$ real matrix, the SVD (Singular Value Decomposition) algorithm is $O(n^3)$. I have large matrices (say $10,000 \times 10,000$) that only have elements on few diagonals, i.e. $M=(m_{i,j})\in \mathbb{R}^{n\times n}$ such that $m_{i,j} =0$ if $|i-j|>k$ ($k$ is set and way smaller than $n$). An, in fact these matrices are highly structured (the are Block Toeplitz with Toeplitz Blocks)

  1. Is there a name to describe such "multi-diagonal matrices" matrices (I know about tridiagonal matrices, and these could be seen as a generalization)?
  2. More importantly, is there a significantly faster SVD algorithm for these matrices?
share|cite|improve this question
Well, for banded (Toeplitz) matrices, are you sure you want all the singular values? Usually a variant of Lanczos can be used for computing the first few singular values of a sparse matrix, see for instance. – J. M. Sep 18 '10 at 1:12
Very useful link, thanks J. M. – Portland Sep 19 '10 at 12:57
Maybe in your application you might also benefit from an approximation to block Toeplitz matrices via Kronecker products, as discussed in:… – Suvrit Oct 5 '10 at 13:25
up vote 1 down vote accepted

It depends on how small $k$ is. If $k^2 \ll n,$ the simple method of computing $M^t M$ (sparsely), then the Cholesky decomposition, then the eigenvalues, works very well. Perhaps less work is using

share|cite|improve this answer

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.