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)

- Is there a name to describe such "multi-diagonal matrices" matrices (I know about tridiagonal matrices, and these could be seen as a generalization)?
- More importantly, is there a significantly faster SVD algorithm for these matrices?

allthe 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