Accession Number : ADA192762

Title :   An O(N2) Method for Computing the Eigensystem of N x N Symmetric Tridiagonal Matrices by the Divide and Conquer Approach.

Descriptive Note : Final rept.,

Corporate Author : INSTITUTE FOR COMPUTER APPLICATIONS IN SCIENCE AND ENGINEERING HAMPTON VA

Personal Author(s) : Gill, Doron ; Tadmor, Eitan

PDF Url : ADA192762

Report Date : Mar 1988

Pagination or Media Count : 25

Abstract : An efficient method is proposed to solve the eigenproblem of N x N Symmetric Tridiagonal (ST) matrices. Unlike the standard eigensolvers which necessitate 0(n-cubed) operations to compute the eigenvectors of such ST matrices, the proposed method computes both the eigenvalues and eigenvectors with only 0(n-squared) operations. The method is based on serial implementation of the recently introduced Divide and Conquer (DC) algorithm. It exploits the fact that by 0(n-squared) of DC operations, one can compute the eigenvalues of N x N ST matrix and a finite number of pairs of successive rows of its eigenvector matrix. The rest of the eigenvectors-all of them or one at the time, are computed by linear three-term recurrence relations. We conclude with numerical examples, which demonstrate the superiority of the proposed method by saving an order of magnitude in execution time at the expense of sacrificing a few orders of accuracy. Keywords: Symmetric eigenvalue problem, Divide and conquer, Updating problem.

Descriptors :   *EIGENVECTORS, *MATRIX THEORY, *MATRICES(MATHEMATICS), ACCURACY, ALGORITHMS, COSTS, EFFICIENCY, EIGENVALUES, SYMMETRY, TIME

Subject Categories : Numerical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE