where Q is unitary and is the diagonal singular value matrix. The computation consists of two stages: Lanczos tridiagonalization and symmetric SVD of a symmetric and tridiagonal matrix. This package extends this method to the general case by performing in the first stage a Lanczos bidiagonalization of a general real matrix followed by the SVD of a square bidiagonal real matrix.
Five Lanczos bidiagonalization functions are provided. The first uses partial orthogonalization, the second uses modified partial orthogonalization and the third uses modified partial orthogonalization with an added restart technique. In general, the modified partial orthogonalization versions are more efficient than the partial orthogonalization version. The modified partial orthoganlization with the restart technique is comparatively more robust. The matrix-vector multiplication in the Lanczos functions can be replaced by a matrix-vector multiplication function to take advantage of the matrix structure. For example, if it is replaced by a fast Hankel matrix-vector multiplication, this package can be used for fast Hankel SVD. Fast Hankel methods are provided for the modified partial orthogonalization and modified partial orthoganlization with restart technique Lanczos methods.
The twisted factorization method for a square bidiagonal real matrix is
provided for the second stage of the SVD. The algorithm skips over small
subdiagonals in order to maintain numerical stability, potentially resulting
in a series of SVDs.
gFHSVDDemo ______________________________________________________________________|___________________ _________|_________________ | | | _______|__________________________ hankelfnrm appsvd gLanPO | | _______|________ gLanMPO gFHLanMPO gFHLanMPOR | | gLanMPOR _____|_____ _____________|______________ gcstsvdt clasv2 | | | | | | | fhmvmtconv fhmvmultiply fhmvmtconv hankelfnrm fhmvmultiply gtwist slasv2 | gcqds
appsvd.m SVD of a bidiagonal matrix using twisted factorization, skipping small subdiagonals. clasv2.m Compute singular value decomposition of 2x2 upper triangular complex matrix. fhmvmtconv.m Converst Hankel matrix to Toeplitz-ciruclant matrix. fhmvmultiply.m Fast general Toeplitz-circulant matrix-vector multiplication. gcqds.m Compute complex quotient-differences with shift for a general matrix, given Cholesky factorization. gcstsvdt.m SVD of an upperbidiagonal matrix using twisted factorization method. gFHLanMPO.m General Fast Hankel Lanczos bidiagonalization with modified partial orthogonalization. gFHLanMPOR.m General Fast Hankel Lanczos bidiagonalization with modified partial orthogonalization and restart. gFHSVDDemo.m Demonstrates general Hankel Lanczos bidiagonalization and SVD. gLanMPO.m General Lanczos bidiagonalization with modified partial orthogonalization. gLanMPOR.m General Lanczos bidiagonalization with modified partial orthogonalization and restart. gLanPO.m General Lanczos bidiagonalization with partial orthogonalization. gtwist.m Compute the corresponding eigenvector using twisted factorization. hankelfnrm.m Compute the Frobenius norm of an m-by-n, m>=n, Hankel matrix. slasv2.m Compute singular value decomposition of a 2-by-2 real upper triangular matrix
Professor, Department of Computing and Software
McMaster University, Hamilton, Ontario L8S 4K1, Canada
(905)-5259140 ext 27234