How can I get eigenvalues and eigenvectors fast and accurate?

Question

I need to compute the eigenvalues and eigenvectors of a big matrix (about 1000*1000 or even more). Matlab works very fast but it does not guaranty accuracy. I need this to be pretty accurate (about 1e-06 error is ok) and within a reasonable time (an hour or two is ok).

My matrix is symmetric and pretty sparse. The exact values are: ones on the diagonal, and on the diagonal below the main diagonal, and on the diagonal above it. Example:

How can I do this? C++ is the most convenient to me.

Answer 1

Your system is tridiagonal and a (symmetric) Toeplitz matrix. I'd guess that eigen and Matlab's eig have special cases to handle such matrices. There is a closed-form solution for the eigenvalues in this case (reference (PDF)). In Matlab for your matrix this is simply:

n = size(A,1);
k = (1:n).';
v = 1-2*cos(pi*k./(n+1));

This can be further optimized by noting that the eigenvalues are centered about 1 and thus only half of them need to be computed:

n = size(A,1);
if mod(n,2) == 0
    k = (1:n/2).';
    u = 2*cos(pi*k./(n+1));
    v = 1+[u;-u];
else
    k = (1:(n-1)/2).';
    u = 2*cos(pi*k./(n+1));
    v = 1+[u;0;-u];
end

I'm not sure how you're going to get more fast and accurate than that (other than performing a refinement step using the eigenvectors and optimization) with simple code. The above should be able to translated to C++ very easily (or use Matlab's codgen to generate C/C++ code that uses this or eig). However, your matrix is still ill-conditioned. Just remember that estimates of accuracy are worst case.

Answer 2

MATLAB does not guarrantee accuracy

I find this claim unreasonable. On what grounds do you say that you can find a (significantly) more accurate implementation than MATLAB's highly refined computational algorithms?

AND... using MATLAB's eig, the following is computed in less than half a second:

%// Generate the input matrix
X = ones(1000);
A = triu(X, -1) + tril(X, 1) - X;

%// Compute eigenvalues
v = eig(A);

It's fast alright!

I need this to be pretty accurate (about 1e-06 error is OK)

Remember that solving eigenvalues accurately is related to finding the roots of the characteristic polynomial. This specific 1000x1000 matrix is very ill-conditioned:

>> cond(A)

ans =
    1.6551e+003

A general rule of thumb is that for a condition number of 10^k, you may lose up to k digits of accuracy (on top of what would be lost to the numerical method due to loss of precision from arithmetic method).

So in your case, I'd expect the results to be accurate up to an approximate error of 10^-3.

Answer 3

If you're not opposed to using a third party library, I've had great success using the Armadillo linear algebra libraries.

For the example below, arma is the namespace they like to use, vec is a vector, mat is a matrix.

arma::vec getEigenValues(arma::mat M) {
    return arma::eig_sym(M);
}

You can also serialize the data directly into MATLAB and vice versa.