where Q is unitary and 
is the diagonal singular
value matrix.
This package of Matlab functions computes the Takagi factorization of a complex-symmetric matrix. The computation consists of two stages: Lanczos tridiagonalization and symmetric SVD of a symmetric and tridiagonal matrix. Three Lanczos tridiagonalization functions are provided. The first uses partial orthogonalization, and the second uses modified partial orthogonalization. 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. Three methods for symmetric SVD of a symmetric and tridiagonal matrix are provided. One uses pure implicit QR method, another uses the divide-and-conquer method and another uses the twisted factorization method. Usually, the twisted factorization method is much faster than the divide-and-conquer method which is in turn usually much faster than the implicit QR method. The implicit QR method uses the order two class two shift, since we implicitly solve a symmetric pentadiagonal eigenvalue problem.
The matrix-vector multiplication in the Lanczos functions can be replaced by
a matrix-vector multiplication function. For example, if it is replaced by
a fast Hankel matrix-vector multiplication, this package can be used for fast
Hankel SVD. If it is replaced by a sparse symmetric matrix-vector
multiplication, this package can be used for sparse symmetric SVD. Since a
Toeplitz matrix can be transformed into a Hankel by reversing its columns or
rows, this package can also be used for fast Toeplitz SVD.
2. Dependency
TakagiDemo
_________ _________________________|____________________________________________________________________________________
| | | | |
csgen LanMPOR cstsvdd (divide-and-conquer) cstsvdt (twisted) CSSVD (QR)
| LanMPO __________|__________ ________________|______________ |
unitarand LanPO | | | | | | cssvdstep
sqevd eig2tak cssing cstlqd twist eig2tak _______|_______
______|_______ | | | | | |
| | cssingstep rotate cqds cssvd2 house shift22
CSSVD sevr _____|_____ | |
______|______ | | csvd2 rotate
| | cssvd2 shift22 _____|_____
deflate slv | | | |
| csvd2 rotate rotate slasv2
rotate ____|____
| |
rotate slasv2
FHSVDDemo
_________________________|___________________________________________________________________________________
| | | |
FHLanMPOR cstsvdd (divide-and-conquer) cstsvdt (twisted) CSSVD (QR)
FHLanMPO __________|__________ ________________|______________ |
| | | | | | | cssvdstep
fhmvmul sqevd eig2tak cssing cstlqd twist eig2tak _______|_______
______|_______ | | | | | |
| | cssingstep rotate cqds cssvd2 house shift22
CSSVD sevr _____|_____ | |
______|______ | | csvd2 rotate
| | cssvd2 shift22 _____|_____
deflate slv | | | |
| csvd2 rotate rotate slasv2
rotate ____|____
| |
rotate slasv2
cqds.m Compute complex quotient-differences with shift, given Cholesky factorization. csgen.m Generate a random complex-symmetric matrix, given its singular values. cssing.m The singular values of a complex symmetric tridiagonal T given by its diagonals. cssingstep.m One QR step in complex symmetric SVD, computes singular values only. CSSVD.m The SVD of a tridiagonal complex-symmetric matrix using implicit QR method with order two class two shifts. cssvd2.m Compute the SVD of a 2-by-2 complex-symmetric matrix. cssvdstep.m One step of the implicit QR method for tridiagonal complex-symmetric matrices using order two class two shift. cstlqd.m Compute the LQ decomposition of a complex-symmetric and tridiagonal matrix. cstsvdd.m The symmetric SVD of a symmetric and tridiagonal matrix using divide-and-conquer method. cstsvdt.m The symmetric SVD of a symmetric and tridiagonal matrix using twisted factorization method. csvd2.m The SVD of a 2-by-2 complex matrix. deflate.m Deflation in the symmetric eigenvalue rank-one modification problem. eig2tak.m Convert eigenvalues and eigenvectors (left singular vectors) into Takagi values and Takagi vectors. FHLanMPO.m Fast Lanczos tridiagonalization of Hankel matrices using the modified partial orthogonalization. FHLanMPOR.m Fast Lanczos tridiagonalization of Hankel matrices using the modified partial orthogonalization and restart. fhmvmul.m Fast Hankel matrix-vector multiplication. FHSVDDemo.m Demonstrate the fast Hankel SVD. house.m Householder transformation given a vector. LanMPO.m Lanczos tridiagonalization of a complex-symmetric matrix using the modified partial orthogonalization. LanMPOR.m Lanczos tridiagonalization of a complex-symmetric matrix using the modified partial orthogonalization and restart. LanPO.m Lanczos tridiagonalization of a complex-symmetric matrix using the partial orthogonalization. rotate.m Rotation transformation given a 2-D vector. sevr.m Symmetric eigen problem rank-one modification. shift22.m Find the order two class two shift. slasv2.m Compute the SVD of a 2-by-2 real and upper triangular matrix. slv.m Secular equation solver. sqevd.m Symmetric pentadiagonal eigenvalue decomposition. The symmetric pentadiagonal matrix is a product of a tridiagonal matrix and its transpose. TakagiDemo.m Demonstrate the Takagi factorization, or symmetric SVD, of a complex-symmetric matrix. twist.m Compute the corresponding eigenvector using twisted factorization. unitarand.m Generate a random unitary matrix.
Professor, Department of Computing and Software
McMaster University, Hamilton, Ontario L8S 4K1, Canada
(905)-5259140 ext 27234