Dominant eigenvectors of an unknown matrix
In the absence of other answers, and sorry if you have already considered this, but the power method can be very fast with a sparse matrix. You may like to check out how Google does it (eigenvectors are used for page rank, which is pretty fast).

http://en.m.wikipedia.org/wiki/PageRank


  Because of the large eigengap of the modified adjacency matrix
  above,[22] the values of the PageRank eigenvector can be approximated
  to within a high degree of accuracy within only a few iterations.


Footnote 22 points to: http: //www-cs-students.stanford.edu/~taherh/papers/secondeigenvalue.pdf

Footnote 23 discusses how to make the calculation even faster
http: //projecteuclid.org/euclid.im/1150474883

I have not read the papers, but I hope that you find one of them to be useful. (I had to break the links as new users can not post many links.)