SVD complexity for structured sparse matrices

Hello,

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?
-
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 sun.stanford.edu/~rmunk/PROPACK 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: citeseerx.ist.psu.edu/viewdoc/… – Suvrit Oct 5 '10 at 13:25

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