Eigenvalues of a tridiagonal matrix

Click For Summary
Algorithms for finding eigenvalues of symmetric matrices often first convert them into tridiagonal form, which retains similarity to the original matrix. Tridiagonal matrices, having significantly fewer non-zero entries, allow for specialized numerical algorithms that enhance efficiency in both computation time and storage. While general algorithms like the QR method can initially disrupt the matrix's sparsity, they can still be adapted to maintain tridiagonality. This adaptation is crucial for preserving the advantages of working with tridiagonal matrices. Efficient algorithms specifically designed for tridiagonal matrices exist, providing substantial computational benefits.
Hassan2
Messages
422
Reaction score
5
Some algorithms of finding the eigenvalues of symmetric matrices first transform the matrix to a tridiagonal matrix which is similar to the original matrix and then find the eigenvalues of the tridiagonal matrix. . Are there special algorithms for a tridiagonal matrix, or do the same algorithms for general matrixes converge faster for a tridiagonal one?

Your help would be appreciated.
 
Physics news on Phys.org
A general n by n matrix has n^2 entries. An n by n "tri-diagonal" matrix has only 3n- 2 entries (not counting the ones that you know are 0 and don't have to keep track of). There are numerical algorithms for working with tri-diagonal matrices that do NOT "fill in the zeros" so, yes, there is an enormous saving in both time and storage working with tri-diagonal matrices.
 
Thanks HalsofIvy,

Do you know any of such algorithms?
The general algorithms that I know, like QR eigenvalue algorithm ,ruin the sparsity of the matrix in the very first iteration. Or maybe I misunderstood it.

Added: There was a mistake in my code. The QR transformation does preserve the tridiagonality.

Thanks again.
 
Last edited:

Thread 'Confusion about the Moyal-Weyl twist'

I am studying the mathematical formalism behind non-commutative geometry approach to quantum gravity. I was reading about Hopf algebras and their Drinfeld twist with a specific example of the Moyal-Weyl twist defined as F=exp(-iλ/2θ^(μν)∂_μ⊗∂_ν) where λ is a constant parametar and θ antisymmetric constant tensor. {∂_μ} is the basis of the tangent vector space over the underlying spacetime Now, from my understanding the enveloping algebra which appears in the definition of the Hopf algebra...
View full post »

Similar threads

Undergrad In 4x4 matrix when does row swapping not affect eigenvaluess?
  • · Replies 6 ·
Replies
6
Views
4K
Undergrad Can one find a matrix that's 'unique' to a collection of eigenvectors?
  • · Replies 33 ·
2
Replies
33
Views
2K
Undergrad How do I know if a matrix is positive definite?
  • · Replies 11 ·
Replies
11
Views
3K
Undergrad Unravelling Structure of a Symmetric Matrix
  • · Replies 5 ·
Replies
5
Views
3K
Undergrad Getting eigenvalues of an arbitrary matrix with programming
  • · Replies 1 ·
Replies
1
Views
2K
What Does Converting a Matrix to Tridiagonal Form Indicate in Practical Terms?
  • · Replies 13 ·
Replies
13
Views
6K
Undergrad Jacobi matrix diagonalization problems
  • · Replies 5 ·
Replies
5
Views
2K
How to Efficiently Solve a Tridiagonal Matrix with Fringes?
  • · Replies 1 ·
Replies
1
Views
3K
Graduate Eigenvalues of block matrix/Related non-linear eigenvalue problem
  • · Replies 1 ·
Replies
1
Views
2K
Undergrad Spectral theorem for Hermitian matrices-- special cases
  • · Replies 2 ·
Replies
2
Views
3K