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

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1988
Accession Number
ADA192762

Entities

People

  • Doron Gill
  • Eitan Tadmor

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Accuracy
  • Algorithms
  • Computations
  • Computers
  • Decomposition
  • Eigenvalues
  • Eigenvectors
  • Engineering
  • Equations
  • Error Analysis
  • Errors
  • Intervals
  • Iterations
  • Precision
  • Quadratic Equations
  • Rational Functions
  • Standards

Readers

  • Applied Combinatorial Optimization and Logic Circuit Design.
  • Calculus or Mathematical Analysis
  • Finite Element Method (FEM) for solving Partial Differential Equations (PDEs)