A fast symmetric SVD algorithm for square Hankel matrices (Q2465321)

A novel symmetric singular value decomposition (SSVD) algorithm for square Hankel matrices of order \(n\) is presented, in contrast to the existing singular value decomposition (SVD) algorithms. A square Hankel matrix is first transformed into a symmetric tridiagonal form using the block Lanczos method integrated with orthogonalization schemes for high performance and good orthogonality. Then the SSVD of the symmetric tridiagonal matrix is computed by the implicit QR method for the singular values and the twisted factorization method for the singular vectors. This method works much faster on special matrices, especially in case of symmetric tridiagonal Hessenberg matrices, and symmetric band matrices. Finally, the singular vectors are converted into the Takagi vectors in the SSVD. The Takagi vector matrix is given in the form of a product of unitary matrices. If the block Lanczos method is used in the tridiagonalization, it is a product of three unitary matrices; if the classical Lanczos method is used, it is a product of two matrices. The issue of the orthogonality of the Takagi vectors associated with a multiple singular value is dealt with by two techniques: an index selection strategy in the twisted factorization method; the orthogonalization process in converting the singular vectors into the Takagi vectors. Some numerical experiments are provided to confirm the theoretical complexity and to illustrate the good accuracy of the proposed algorithm.