
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(ncubed) operations to compute the eigenvectors of such ST matrices, the proposed method computes both the eigenvalues and eigenvectors with only 0(nsquared) operations. The method is based on serial implementation of the recently introduced Divide and Conquer (DC) algorithm. It exploits the fact that by 0(nsquared) 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 eigenvectorsall of them or one at the time, are computed by linear threeterm 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