JuliaLang/julia — pull request #5759 by andreasnoackjensen (2014-02-10 22:22:56+00:00)
Title: WIP: SymTridiagonal eigensolver

Just to open the discussion about how we should do the `SymTridiagonal`. The eigen solver works well when it only uses QL steps. The first is LAPACK and the second is the new julia implementation.
```
julia> A=SymTridiagonal(randn(5000),randn(4999));

julia> @time eigvals(A);
elapsed time: 0.912759657 seconds (160368 bytes allocated)

julia> @time Base.LinAlg.eigvals!(copy(A));
elapsed time: 1.91420947 seconds (200408 bytes allocated)
```
LAPACK tries to be clever and switch between QR and QL, but for me, the QR doesn't give fast convergence.

I didn't use the `Givens` type because I wanted to see how fast I could make it and also because I couldn't use the `A_mul_B` methods anyway. There is no room for the bulge in a `SymTridiagonal`.

We also have to consider the vectors. There are at least two options for handling the vectors. We could do the same as LAPACK and apply the rotations in each step, or we could accumulate `Givens` matrices in a `Rotation`. We should probably also introduce a `SymmetricTridiagonalFactorization` immutable to keep track of all the pieces.