Decreasing computation time to get the eigenvalues of H

[cgyurgyik]

So just running some quick trials,

n = 10000; 
H = randn(n,n); 
H = (H+H')/2; 

disp('eig');
tic;
for k = 1:5
    [eigenvectors, ~] = eig(H);
end
toc;

H = randn(n,n); 
H = (H+H')/2; 

disp('GEFE');
tic;
for k = 1:5
    ev_of_H = GetEigenvectorFromEigenvalues(H,1,1);
toc;
end

(eig) Elapsed time is 185.192800 seconds.
(GEFE) Elapsed time is 119.087356 seconds.

So yes, GEFE is faster (as you claimed) to find the value of the ith row and jth column of an eigenvector for very large matrices. (One small catch here is GEFE provides normed values while eig does not).

It does exactly that, only finds the ith row and jth column value of an eigenvector. If we wanted to find, say, two values, you're essentially 'doubling' the time. (Well, we can provide an optional argument to the function where the user can provide the eigenvalues, so that they aren't computed for H each time.) On the other hand, eig provides ALL the eigenvectors.

So applying Amdahl's law, I suspect the largest chunk of computation time for GEFE goes to getting the eigenvalues of H and hj using eig(). The question then, is there a faster way to provide the eigenvalues of a matrix, when we don't exactly need the eigenvectors?

What I know:

• eig(A) uses cholesky or shur decompositions.
• svd(A) was even slower, at least for Hermitian matrices.
• svds(A, k) provides the largest eigenvalues, and was even slower when setting k = n.
• Just through some quick google searches, I saw the bisection algorithm and the power method. From what I understand, the power method doesn't fair too well with large matrices.

[ajt60gaibb]

I changed the algorithm in GetEigenvectorFromEigenvalues so that the cost of computing one entry of v_j or 10 entries is essentially the same.

[cgyurgyik]

I thought about this, and I'm attempting to provide an optional argument so that the user can compute his or her own eigenvalues. Overloaded functions in Matlab aren't the prettiest in terms of readability (or maybe there is a better way), but eig() may not always be the best choice for the client to produce his or her eigenvalues. Could also apply this to hj.

Another way to provide the client the bare bones application is to allow him or her to pass in the function to compute the eigenvalues (Pass in a function as an optional argument). Not sure which is better for MATLAB applications.