Most efficient method for computing Singular Value Decomposition of a triangular matrix?
Solution 1:
My recommendation would be to use Cholesky decomposition of the matrix $AA^T$. For an upper-triangular matrix $A$ the Cholesky decomposition of $AA^T$ is obviously trivial.
And then there exist several algorithms for finding the singular values given the Cholesky decomposition. I was trying to think of one myself, but apparently someone has already written a paper about it, which I imagine would be of more use to you:
http://arxiv.org/pdf/1202.1490.pdf
In any case, the Cholesky decomposition seems like the best framework for utilizing the structure of the matrix $AA^T$ when A is upper-triangular.
More references:
http://www.maths.manchester.ac.uk/~nstrabic/talks/chol_en.pdf
Relation between Cholesky and SVD
Solution 2:
Stardard algorithms for computing SVD factorization of an $m \times n$ matrix A process in two steps:
- bidiagonalization of A
- SVD factorization of bidiagonal matrix using QR method or divide-and-conquer.
The bidiagonalization procedure cannot utilize the triangular structure of A, and therefore standard SVD solvers cannot be optimized for triangular matrices.
However the Jacobi method can be optimized for triangular matrices, see MLA Drmac, Zlatko, and Krešimir Veselic. "New fast and accurate Jacobi SVD algorithm. II." SIAM Journal on Matrix Analysis and Applications 29.4 (2008): 1343-1362; also Lapack Working Note 170.
To my knowledge, this optimization was not implemented and it is hard to say if this method would be faster, than methods for general matrices. Jacobi method is slower than divide-and-conquer for general matrices, so it may be still slower for triangular matrices.