Dear Muhammad,

in my opinion Krylov type methods are suitable for your problem.

Greetings, Tadeusz

You probably need some Lanczos-type method. What method to choose depends on the problem, its structure and its origin. Does it come from a self-adjoint differential operator? 

The lecture notes by Prof Arbenz at ETH is state-of-the-art

http://people.inf.ethz.ch/arbenz/ewp/Lnotes/lsevp.pdf

Rational Canonical Form (RCF) can be useful for this problem. After diagonal matrix obtain by the method, eigenvalues can be found easily.

http://www.math.uiuc.edu/~rotman/book.pdf