Fast methods for approximating the highest 3 eigenvalues and eigenvectors of a large symmetric matrix

Question

I am writing code to compute Classical Multidimensional Scaling (abbreviated to MDS) of a very large n by n matrix, n = 500,000 in my example.

In one step of MDS, I need to compute the highest three eigenvalues and their corresponding eigenvectors of a n by n matrix. This matrix is called the B matrix. I only need these three eigenvectors and eigenvalues. Common methods of calculating eigenvectors and eigenvalues of a large matrix take a long time, and I do not require a very accurate answer, so I am seeking an estimation of the eigenvectors and eigenvalues.

Some parameters:

1. The B matrix is symmetric, real, and quite dense
2. The eigenvalue decomposition of B in theory should always produce real numbers.
3. I do not require an entirely precise estimation, just a fast one. I would need it to complete in several hours.
4. I write in python and C++

My question: Are there fast methods of estimating the three highest eigenvectors and eigenvalues of such a large B matrix?

My progress: I have found a method of approximating the highest eigenvalue of a matrix, but I do not know if I can generalize it to the highest three. I have also found this paper written in 1996, but it is extremely technical and hard for me to read.

Answer 1

G. Golub and C.F Van Loan Matrix Computations 2nd in chapter 9 state that Lanczos algorithms are one choice for this (except that the matrix should ideally be sparse - it clearly works for non-sparse ones as well)

https://en.wikipedia.org/wiki/Lanczos_algorithm