0

There was a similar question: How expensive is it to compute the eigenvalues of a matrix?

And the answer was big-Oh(n^3) for square and symmetric matrices.

What about the largest eigenvalue and corresponding eigenvector of n-by-n matrix?

Here I assume that matrix is square and Hermitian. I think it is still must be faster than big-Oh(n^3) because we are interested only on the largest eigenvalue and the corresponding eigenvector.

This is the Matlab code that I currently use, but I don't think it is best, because I still compute all eigenvalues instead of largest and sort them.

A=2.*rand(3,3)-1*ones(3,3)+i*(2.*rand(3,3) -1*ones(3,3));
[v,e]=eig(A+A');
[d,ind] = sort(diag(e),'descend');
e=d(1)
v = v(:,ind);
v(1:3,1)
Lee
  • 169
  • 1
  • 9
  • 1
    Use the function `eigs()` where you can choose how many eigenvalues you want out. It has a bibliographic reference in the docs, but I believe it does only compute the ones you ask, no idea about the algorithm O() though. – Ander Biguri Sep 17 '21 at 08:24

1 Answers1

0

Try this:

A=2.*rand(3,3)-1*ones(3,3)+i*(2.*rand(3,3) -1*ones(3,3));
[v,e]=eigs(A+A',1,'largestabs');

Please, let me know how it goes!

Juan David Navarro
  • 11
  • 4
  • Thank for your answer. I think this code gives largest eigenvalue by magnitude, not the actual largest eigenvalue. Anyway, my question is more related to the computational complexity, I am wondering how fast it is possible to calculate the largest eigenvalue and corresponding eigenvector. – Lee Sep 19 '21 at 08:36
  • I think it depends on the eigensolver you want to use and the properties of the matrix you are using. In my experience, the traditional QR algorithm converges in n^3, but then, it will give you all the eigenvalues, other methods add variations on this method (QZ, subspace, lanczos, etc...) and use properties from the matrix to reduce the number of operations (i.e. using the hassenberg representation) – Juan David Navarro Sep 19 '21 at 20:32
  • I can recommend several references on this topic: [1] Tzounas, G., Dassios, I., Liu, M., and Milano, F., 2020, “Comparison of Numerical Methods and Open-Source Libraries for Eigenvalue Analysis of Large-Scale Power Systems,” Appl. Sci., 10(21), p. 7592. [2] Golub, G. H., and Van Loan, C. F., 2013, Matrix Computations, The Johns Hopkins University Press. [3] Trefethen, L. N., & Bau III, D. (1997). Numerical linear algebra (Vol. 50). Siam. – Juan David Navarro Sep 19 '21 at 20:39
  • [4] Moler, C. B., & Stewart, G. W. (1973). An algorithm for generalized matrix eigenvalue problems. SIAM Journal on Numerical Analysis, 10(2), 241-256. I have a discussion myself on a coming paper: Navarro, J. D, et. al. Arbitrary-Order Sensitivity Analysis in Phononic Metamaterials Using the Multicomplex Taylor Series Expansion Method Coupled with Bloch's Theorem, Journal of Applied Mechanics, – Juan David Navarro Sep 19 '21 at 20:40