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

Abstract

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.