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