No effect is observed when I try to use StartVector in eigs to improve numerical efficiency

I test the efficiency of using a good StartVector in eigs.

The code is quite simple.

First, I use eigs to figure out the eigenvector v1,

then I use this eigenvector v1 as the StartVector to run eigs again.

I expect that much less time might be needed now.

Nevertheless,

the time cost shows no improvement at all.

My code is as follows

----------------------------------------------------------------------

format long
    
    n = 3000;
    A = rand(n,n);
    A = A + A';
    
    tic
    [v1,eta1]=eigs(@(vec)test_eigs(vec,A),n,1,'lm','Display',0,'IsFunctionSymmetric',0,'MaxIterations',300);
    toc
    
    StartVector = v1;
    tic
    [v2,eta2]=eigs(@(vec)test_eigs(vec,A),n,1,'lm','Display',0,'IsFunctionSymmetric',0,'MaxIterations',300,'StartVector',StartVector);
    toc
    
    eta1
    eta2
    
    function vec1 = test_eigs(vec0,A)
    vec1 = A * vec0;
    end

------------------------------------------------------------------------------------

The output is as follows

~~~~~~~~~~~~~~~~~~~~~~

    Elapsed time is 0.069811 seconds.
    Elapsed time is 0.066047 seconds.
    
    eta1 =
    
         3.000980119229400e+03
    
    
    eta2 =
    
         3.000980119229400e+03

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

So my question is,

is there anything wrong in my understanding about StartVector in eigs?

Any suggestion or comment would be greatly appreciated.

[Umar]

Hi Zhao,

Your understanding of StartVector in eigs appears to be generally accurate, there are various considerations and potential optimizations to explore further to address the efficiency issue you are experiencing. After analyzing your code snippet, the elapsed times for computing eigenvectors with and without the StartVector are quite close, indicating that the initial guess (v1) might already be close to the actual eigenvector. This scenario explains why there is no noticeable time improvement when using the StartVector. To enhance efficiency using StartVector, consider scenarios where the initial guess is far from the actual eigenvector, leading to quicker convergence. Also, experimenting with different initial guesses or refining the eigenvector computation process may yield more noticeable efficiency gains. I made some changes to your code snippet to make it more efficient in terms of computation time as it eliminates the need for the test_eigs function and achieves faster results but feel free to customize it based on your needs.

format long

% Define matrix A n = 3000; A = rand(n,n); A = A + A';

% Compute eigenvector v1 without StartVector tic [v1, eta1] = eigs(A, 1, 'lm', 'Display', 0); toc

% Use eigenvector v1 as StartVector for eigs StartVector = v1; tic [v2, eta2] = eigs(A, 1, 'lm', 'Display', 0, 'StartVector', StartVector); toc

% Display eigenvalues eta1 eta2

Please see attached results.

Please let me know if you have any further questions.

[David Goodmanson]

Hi ZS,

eigs finds the eigenvectors corresponding to one or a few eigenvalues of largest absolute value. Since eigs presumably has no way to know that the supplied StartVector has an eigenvalue of largest absolute value, it's not so clear how supplying that vector would help.

[Zhao-Yu]

Hi David,

Thank you very much for your comment.

Do you suggest that we could not reduce the computation time for calculating the lead eigenvalue/eigenvector by supplying 'StartVector', even if we kown this eigenvector ?

Is this a shortcoming of eigs? Then why eigs offers 'StartVector' for users ?

I ask this question, because in most eigenvalue solvers, offering a good guess of the eigenvector can improve the speed of convergence.

[Umar]

Hi Zhao,

You asked some really good questions. Please see my response to your questions below.

Do you suggest that we could not reduce the computation time for calculating the lead eigenvalue/eigenvector by supplying 'StartVector', even if we kown this eigenvector ?

No, that is not correct. By providing an initial estimate close to the actual eigenvector, the computation process can converge faster, leading to reduced computational overhead. However, it may not always guarantee a significant reduction in computation time, especially if the initial guess is not sufficiently accurate or if the problem is inherently complex.

Is this a shortcoming of eigs? Then why eigs offers 'StartVector' for users ?

It is not a shortcoming but rather a feature that allows users to provide an initial guess for the eigenvectors. Also, eigs offering the 'StartVector' parameter will help users influence the convergence behavior of the algorithm and potentially speed up the computation process by providing a good estimate of the eigenvectors.

It is particularly useful when you have prior knowledge about the structure of the eigenvectors or want to guide the algorithm towards specific solutions. Please let me know if you have any further questions.

[Zhao-Yu]

Dear Umar,

Thank you for your comments,

and I would like to say sorry for this late reply.

I did not response to you because, when I run your script,

I did not see any significant speed up by supplying the guess eigenvector.

When your script is called for the first time,

it indeed present some cost difference, i.e.,

0.34 seconds (without supplying the guess eigenvector)

vs 0.078 seconds (with supplying the precise eigenvector):

-----------------time cost when runing for the first time-------------

Elapsed time is 0.340024 seconds.

Elapsed time is 0.077819 seconds.

--------------------------------------------------------------------------------

Nevertheless, when I run the script again for many times,

the time cost always looks like:

------------------time cost when runing again-------------------------

Elapsed time is 0.065735 seconds.

Elapsed time is 0.066109 seconds.

--------------------------------------------------------------------------------

Thus,

I believe the huge time cost (i.e., 0.34 seconds) may result from loading eigs into memory.

And generally speaking,

I still observe that supplying a good guess eigenvector does not speed up the convergence in eigs.

Thank you very much for your patience.

[Umar]

Hi Zhaou,

No worries. I read your comments and you are on the right track with your analysis of the code. However, providing a guess eigenvector in eigs can indeed speed up convergence in certain cases, but its impact may vary depending on the problem and the quality of the guess. The behavior observed could be influenced by factors such as matrix size, eigenvalue distribution, and algorithm settings. It's essential to consider the specific characteristics of the problem to determine the effectiveness of supplying a guess eigenvector. Additionally, optimizing memory usage and algorithm parameters may further enhance performance. Experimenting with different scenarios and tuning parameters could help in achieving better convergence speeds in eigs.

Please correct me if I am wrong, are you seeking algorithm or function in matlab to improve numerical efficiency?

[Zhao-Yu]

Hi Dear Umar,

Thank you very much for your patience and kindness :)

Yes I am trying to improve the numerical efficiency of my code,

which carries out a numerical optimization by solving serials of eigenvalue problems.

In order to improve the efficiency of the code, I tried to use MATLAB coder, but I failed :(

[Umar]

Hi Zhao,

Please don’t give up on your problem. After going through your insights and analysis of StartVector, it made me realize that you have potential to solve this problem. There are other functions and algorithms to help solve this problem and there is always various ways to solve a problem and get solution. So, I will encourage you to keep seeking solution to this problem. Again, if you still need our help, please let us know. We will be more happy to help you out.

Answer 1

[Kaustab Pal]

Hi @Zhao-Yu,

Your understanding of using StartVector is correct. The StartVector serves as the initial guess for the iterative algorithms used by eigs to find the eigenvalues and eigenvectors. A good initial guess can significantly speed up the convergence of the algorithm, while poor initial guesses might lead to slower convergence or convergence to unwanted eigenvalues.

However, please note that the benefit of using the StartVector is especially pronounced when dealing with large sparse matrices. In such cases, the speedup from using StartVectors is significant compared to not using them.

I tested this with a slight modification of the code you provided. You can find the code snippet along with the computation times below.

n = 10000; 

A = rand(n,n); 
A = A + A'; 

A_sparse = sparse(diag(1:n)); 

disp("Computation time without Start Vector for matrix A"); 

Computation time without Start Vector for matrix A

tic 
[V, D] = eigs(@(vec)test_eigs(vec,A),n,1, 'lm','Display',0,'IsFunctionSymmetric',0,'MaxIterations',300);  
toc 

Elapsed time is 0.368794 seconds.

disp("Computation time with Start Vector for matrix A"); 

Computation time with Start Vector for matrix A

tic
[V, D] = eigs(@(vec)test_eigs(vec,A),n,1, 'lm','Display',0,'IsFunctionSymmetric',0,'MaxIterations',300, 'StartVector', V); 
toc 

Elapsed time is 0.319875 seconds.

disp("Computation time without Start Vector for matrix A_sparse"); 

Computation time without Start Vector for matrix A_sparse

tic 
[V_sparse, D] = eigs(@(vec)test_eigs(vec,A_sparse),n,1, 'lm','Display',0,'IsFunctionSymmetric',0,'MaxIterations',300); 
toc 

Elapsed time is 0.591944 seconds.

disp("Computation time with Start Vector for matrix A_sparse"); 

Computation time with Start Vector for matrix A_sparse

tic 
[V_sparse, D] = eigs(@(vec)test_eigs(vec,A_sparse),n,1, 'lm','Display',0,'IsFunctionSymmetric',0,'MaxIterations',300, 'StartVector', V_sparse);
toc 

Elapsed time is 0.021382 seconds.

function vec1 = test_eigs(vec0,A) 
    vec1 = A * vec0; 
end 

As can be seen from the outputs, the computation time when using the StartVector to find the eigenvectors for a large sparse matrix is significantly faster than without using the StartVector.

For more information you can refer to the documentation here: https://www.mathworks.com/help/releases/R2024a/matlab/ref/eigs.html#namevaluepairarguments:~:text=StartVector%20%E2%80%94%20Initial%20starting%20vector

I hope this clarifies your understanding.

[Zhao-Yu]

Hi Dear Kaustab Pal,

I have checked your script for many times,

and the time cost is indeed the same as you:

---------------------------------------------------------------------------

Computation time without Start Vector for matrix A

Elapsed time is 0.621284 seconds.

Computation time with Start Vector for matrix A

Elapsed time is 0.626303 seconds.

Computation time without Start Vector for matrix A_sparse

Elapsed time is 0.464736 seconds.

Computation time with Start Vector for matrix A_sparse

Elapsed time is 0.032755 seconds.

---------------------------------------------------------------------------

Thus, it is quite clear that

(1) When sparse large matrices are involved,

supplying a good guess vector can indeed speed up the convergence sigfinicantly.

(2) For dense matrices,

numerical simulations suggest that supplying a good guess vector to eigs may not speed up the convergence.

Thank you.