Symmetric singular value decomposition of complex symmetric matrices.

摘要

Complex symmetric matrices arise from many applications, such as nuclear magnetic resonance, complex-value independent component analysis and so on. Singular value decomposition (SVD) is an important matrix decomposition in numerical linear algebra. When the matrix is complex symmetric, it has a special form of SVD, symmetric SVD (SSVD) or Takagi factorization. Exploiting this special form, we can save at least half running time and storage space for computing the SVD. However, LAPACK and Matlab do not support this special structure.; In this thesis, we will show how to compute the SSVD of a complex symmetric matrix efficiently. The new algorithms are at least two times faster than the existing svd subroutine in Matlab and five times faster than the implicit QR method. The speedup of our new methods will be even higher when matrix has some special structures, such as Hankel and sparse.; There are two stages for the SSVD, tridiagonalization and diagonalization. We use the block Lanczos method to tridiagonalize a complex symmetric matrix A, rather than the single-vector Lanczos method. The advantage of the block Lanczos method is to speed up the tridiagonalization through exploiting the memory hierarchy.; The second stage of the SSVD is the diagonalization of a complex symmetric tridiagonal matrix. We propose two methods to implement the diagonalization, divide-and-conquer and twisted factorization methods. The divide and-conquer method computes the SSVD of a big matrix through combining the results obtained from small subproblems via rank one modifications. The twisted factorization method provides an efficient method for computing all the Takagi vectors within O(n2) flops when all the singular values are available. As we know the cost of computing all singular values only via the implicit QR method is O(n 2). Thus, we find a method which computes the SSVD of a complex symmetric tridiagonal matrix in O(n2) totally.; A complex Hankel matrix is symmetric, moreover, the complexity of block Lanczos tridiagonalization method for a Hankel matrix is O( n2 log n), rather than O (n3). Combining the implicit QR method for computing the singular values and the twisted factorization method for computing the singular vectors of a complex symmetric tridiagonal matrix, we obtain an O(n2 log n) SVD algorithm for complex Hankel matrices. To our best knowledge, this is the first fast SVD algorithm for Hankel matrices.