Editing Eigenvalue algorithm (section)

==Hessenberg and tridiagonal matrices==

{{main|Hessenberg matrix}}

Because the eigenvalues of a triangular matrix are its diagonal elements, for general matrices there is no finite method like [[gaussian elimination]] to convert a matrix to triangular form while preserving eigenvalues. But it is possible to reach something close to triangular. An [[Hessenberg matrix|upper Hessenberg matrix]] is a square matrix for which all entries below the [[subdiagonal]] are zero. A lower Hessenberg matrix is one for which all entries above the [[superdiagonal]] are zero. Matrices that are both upper and lower Hessenberg are [[Tridiagonal matrix|tridiagonal]]. Hessenberg and tridiagonal matrices are the starting points for many eigenvalue algorithms because the zero entries reduce the complexity of the problem. Several methods are commonly used to convert a general matrix into a Hessenberg matrix with the same eigenvalues. If the original matrix was symmetric or Hermitian, then the resulting matrix will be tridiagonal.

When only eigenvalues are needed, there is no need to calculate the similarity matrix, as the transformed matrix has the same eigenvalues. If eigenvectors are needed as well, the similarity matrix may be needed to transform the eigenvectors of the Hessenberg matrix back into eigenvectors of the original matrix.

{| class="wikitable" style="text-align: center"
|-
! Method !! Applies to !! Produces !! Cost without similarity matrix !! Cost with similarity matrix !! Description
|-
| [[Householder transformation]]s || General || Hessenberg || {{math|{{frac|2''n''<sup>3</sup>|3}} + ''O''(''n''<sup>2</sup>)}}<ref name=NumericalRecipes>{{cite book
| last1 = Press
| first1 = William H.
| last2 = Teukolsky
| first2 = Saul A.
| last3 = Vetterling
| first3 = William T.
| last4 = Flannery
| first4 = Brian P.
| title = Numerical Recipes in C
| url = https://archive.org/details/numericalrecipes00pres_0
| url-access = registration
| edition = 2nd
| year = 1992
| publisher = Cambridge University Press 
| isbn = 978-0-521-43108-8
}}</ref>{{rp|page=474}} || {{math|{{frac|4''n''<sup>3</sup>|3}} + ''O''(''n''<sup>2</sup>)}}<ref name=NumericalRecipes />{{rp|page=474}} || align="left" | Reflect each column through a subspace to zero out its lower entries.
|-
| [[Givens rotation]]s || General  || Hessenberg || {{math|{{frac|4''n''<sup>3</sup>|3}} + ''O''(''n''<sup>2</sup>)}}<ref name=NumericalRecipes />{{rp|page=470}} ||  || align="left" | Apply planar rotations to zero out individual entries. Rotations are ordered so that later ones do not cause zero entries to become non-zero again. 
|-
| [[Arnoldi iteration]] || General || Hessenberg ||  || || align="left" | Perform Gram–Schmidt orthogonalization on Krylov subspaces.
|-
| [[Lanczos algorithm]] || Hermitian || Tridiagonal ||  ||  || align="left" | Arnoldi iteration for Hermitian matrices, with shortcuts. 
|}

For symmetric tridiagonal eigenvalue problems all eigenvalues (without eigenvectors) can be computed numerically in time O(n log(n)), using bisection on the characteristic polynomial.<ref name=CoakleyRokhlin>{{Citation |last=Coakley|first=Ed S. |title=A fast divide-and-conquer algorithm for computing the spectra of real symmetric tridiagonal matrices. |journal=[[Applied and Computational Harmonic Analysis]] |volume=34 |issue=3 |date=May 2013 |pages=379–414 |doi=10.1016/j.acha.2012.06.003|doi-access= }}</ref>