Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?
share|improve this question
2  
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
1  
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
add comment

1 Answer

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

http://soi.stanford.edu/~rmunk/PROPACK/

share|improve this answer
add comment

Your Answer

 
discard

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.