Divide-and-conquer eigenvalue algorithm
Divide-and-conquer eigenvalue algorithms are a class of eigenvalue algorithms for Hermitian or real symmetric matrices that have recently (circa 1990s) become competitive in terms of stability and efficiency with more traditional algorithms such as the QR algorithm. The basic concept behind these algorithms is the divide-and-conquer approach from computer science. An eigenvalue problem is divided into two problems of roughly half the size, each of these are solved recursively, and the eigenvalues of the original problem are computed from the results of these smaller problems.
- Comment
- enDivide-and-conquer eigenvalue algorithms are a class of eigenvalue algorithms for Hermitian or real symmetric matrices that have recently (circa 1990s) become competitive in terms of stability and efficiency with more traditional algorithms such as the QR algorithm. The basic concept behind these algorithms is the divide-and-conquer approach from computer science. An eigenvalue problem is divided into two problems of roughly half the size, each of these are solved recursively, and the eigenvalues of the original problem are computed from the results of these smaller problems.
- Depiction
- Has abstract
- enDivide-and-conquer eigenvalue algorithms are a class of eigenvalue algorithms for Hermitian or real symmetric matrices that have recently (circa 1990s) become competitive in terms of stability and efficiency with more traditional algorithms such as the QR algorithm. The basic concept behind these algorithms is the divide-and-conquer approach from computer science. An eigenvalue problem is divided into two problems of roughly half the size, each of these are solved recursively, and the eigenvalues of the original problem are computed from the results of these smaller problems. Here we present the simplest version of a divide-and-conquer algorithm, similar to the one originally proposed by Cuppen in 1981. Many details that lie outside the scope of this article will be omitted; however, without considering these details, the algorithm is not fully stable.
- Hypernym
- Algorithms
- Is primary topic of
- Divide-and-conquer eigenvalue algorithm
- Label
- enDivide-and-conquer eigenvalue algorithm
- Link from a Wikipage to another Wikipage
- Arnoldi iteration
- Big O notation
- Block diagonal matrix
- Category:Divide-and-conquer algorithms
- Category:Numerical linear algebra
- Computational complexity theory
- Computer science
- Diagonalizable matrix
- Divide and conquer algorithm
- Eigenvalue
- Eigenvalue algorithm
- Eigenvector
- File:Almost block diagonal.png
- File:Block diagonal plus correction.png
- Floating point
- Hermitian matrix
- Householder reflection
- LAPACK
- Linear algebra
- Master theorem (analysis of algorithms)
- Newton's method
- Nonlinear
- Numerical stability
- Numerische Mathematik
- Parallel algorithm
- QR algorithm
- Rank (linear algebra)
- Rational function
- Real number
- Recurrence relation
- Recursion
- Society for Industrial and Applied Mathematics
- Symmetric matrix
- Tridiagonal matrix
- SameAs
- 4ieMR
- Algoritmo eigenvalue divide y vencerás
- m.0466xq
- Q5283998
- Subject
- Category:Divide-and-conquer algorithms
- Category:Numerical linear algebra
- Thumbnail
- WasDerivedFrom
- Divide-and-conquer eigenvalue algorithm?oldid=1103119312&ns=0
- WikiPageLength
- 10627
- Wikipage page ID
- 1103352
- Wikipage revision ID
- 1103119312
- WikiPageUsesTemplate
- Template:Citation
- Template:Citation needed
- Template:Cite journal
- Template:Numerical linear algebra
