ABSTRACT
The eigenvalue decomposition (EVD) is an infinite iterative procedure — finding eigenvalues is equivalent to finding zeros of the characteristic polynomial, and, by the results of Abel and Galois, there is no algebraic formula for roots of the polynomial of degree greater than four. However, the number of arithmetic operations required to compute EVD to some prescribed accuracy is also finite — EVD of a general symmetric matrix requires O (n 3) operations, while for matrices with special structure this number can be smaller. For example, the EVD of a tridiagonal matrix can be computed in O (n 2) operations (see Sections 42.5 and 42.6).
