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

Question

Zhao-Yu 2024-7-14

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2137133-no-effect-is-observed-when-i-try-to-use-startvector-in-eigs-to-improve-numerical-efficiency

评论： Umar 2024-7-18

在 MATLAB Online 中打开

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.

8 个评论
显示 6更早的评论隐藏 6更早的评论

Umar 2024-7-14

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.

Umar 2024-7-17

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 2024-7-17

编辑：Zhao-Yu 2024-7-17

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.

Zhao-Yu 2024-7-18

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 2024-7-18

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 2024-7-17

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/2137133-no-effect-is-observed-when-i-try-to-use-startvector-in-eigs-to-improve-numerical-efficiency#answer_1486467

在 MATLAB Online 中打开

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.

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Zhao-Yu 2024-7-17

编辑：Zhao-Yu 2024-7-17

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.

请先登录，再进行评论。

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

8 个评论
显示 6更早的评论隐藏 6更早的评论

回答（1 个）

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

另请参阅

类别

标签

产品

版本

Community Treasure Hunt

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

8 个评论 显示 6更早的评论隐藏 6更早的评论

回答（1 个）

1 个评论 显示 -1更早的评论隐藏 -1更早的评论

另请参阅

类别

标签

产品

版本

Community Treasure Hunt

8 个评论
显示 6更早的评论隐藏 6更早的评论

1 个评论
显示 -1更早的评论隐藏 -1更早的评论