A twisted factorization method for complex symmetric tridiagonal eigenvalue decomposition

We present a twisted factorization algorithm for computing the eigenvectors of an n-by-n nondefective irreducible complex symmetric tridiagonal matrix, given computed eigenvalues. Our algorithm requires 0(n ² ) flops for all the eigenvectors when the multiplicities of the eigenvalues are not large. Since all the eigenvalues of a complex symmetric tridiagonal matrix can be computed in 0(n ²) flops, our algorithm leads to a complete eigenvalue decomposition in 0(n ³) flops, instead of the usual 0(n ³) flops, when the multiplicities of eigenvalues are not large. We also analyze the accuracy and complex orthogonality of the eigenvectors obtained from our algorithm. Our analysis shows that our algorithm is accurate and stable when the given computed eigenvalues are accurate. Finally, our experiments show that our algorithm is much more efficient than the MATLAB built-in subroutine, which is based on the eigenvalue decomposition subroutine in LAPACK. ©2012 International Information Institute.