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?
  • 2
    $\begingroup$ 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. $\endgroup$ – J. M. isn't a mathematician Sep 18 '10 at 1:12
  • 1
    $\begingroup$ 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/… $\endgroup$ – 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



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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