Parallel Divide and Conquer Algorithms for the Symmetric Tridiagonal Eigenproblem and Bidiagonal Singular Value Problem

Download
Author
Borges, Carlos F.
Gragg, William B.
Thornton, John R.
Warner, Daniel D.
Date
1993-06-10Metadata
Show full item recordAbstract
Recent advances [2, 7, 9, 13] can improve run times for certain matrix eigen-value problems by orders of magnitude. In this paper we consider applying permutations to real symmetric tridiagonal matrix T to produce a bordered symmetric matrix with two tridiagonal blocks on its diagonal. The spectra decompositions of the tridiagonal blocks are found recursively and then combined with the border to produce a symmetric arrow matrix A. The eigenvalues of A are the zeros of a rational function, f, and are interlaced by the poles, which are the eigenvalues of the unbordered matrix. The eigenvalues of A can be found using a novel zero finder with global monotone cubic convergence. The zero finder can be started at either of the two poles which the zero interlaces. The eigenvectors of A are found by formulas and the spectral decomposition of T can then be computed directly. The bidiagonal singular value problem is equivalent with the ease in which T has a zero diagonal. In this important special case the subproblems retain this structure.
Rights
This publication is a work of the U.S. Government as defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.Collections
Related items
Showing items related by title, author, creator and subject.
-
Spectral graph theory of the Hypercube
Florkowski, Stanley F. (Monterey, California. Naval Postgraduate School, 2008-12);In Graph Theory, every graph can be expressed in terms of certain real, symmetric matrices derived from the graph, most notably the adjacency or Laplacian matrices. Spectral Graph Theory focuses on the set of eigenvalues ... -
Block Lanczos algorithm.
Kim, Yong Joo (Monterey, California. Naval Postgraduate School, 1989-12);We use a block Lanczos algorithm for computing a few of the smallest eigenvalues and the corresponding eigenvectors of a large symmetric matrix rather than computing all the eigenvalue-eigenvector pairs. The basic Lanczos ... -
On computing accurate singular values and eigenvalues of acyclic matrices
Demmel, J. W.; Gragg, William B. (Monterey, California. Naval Postgraduate School, 1992-08); NPS-MA-92-010It is known that small relative perturbations in the entries of a bidiagonal matrix only cause small relative perturbations in its singular values, independent of the values of the matrix entries. In this paper we show ...