Dear Gul Jokhio

A similar question was raised on March 3, 2018, at the RG platform.

( What are the numerical methods to find the eigen values of a ...

www.researchgate.net › post › What_are_the_numerical_...Is there any general (so called) method by which one can find the eigen values of matrix? )

You may find the answers there are useful.

Regards

MATLAB is the simplest way for computing any matrix analysis, or for your query : spectral decompositions: https://au.mathworks.com/help/matlab/ref/eig.html

Check this old post too:

https://www.researchgate.net/post/How_calculate_eigenvalues_vectors_for_large_scale_matrices

For dense matrices that fit into computer memory, one is unlikely to best the function eig, available in MATLAB and SciPy. This function uses an algorithm that transforms the matrix into a three-diagonal one, the eigenvalues of which are then computed by QR-algorithm (there is a faster alternative to QR known as "divide-and-conquer", but it is less reliable). One notable exception is the eigenvalue problem that arises when one does Principal Component Analysis for a dataset with large amount of nearly redundant data via truncated Singular Value Decomposition. MATLAB/SciPy eig computes all eigenvalues and eigenvectors to machine precision, whereas just a fraction of them computed to low accuracy may be sufficient for PCA. In this case, block iterative algorithms employed by scikit-learn function PCA and raleigh function pca can be much more efficient (both mentioned Python packages are available in PyPI and can be easily installed by pip).

For large sparse matrices, matrix transformation methods, even if possible at all, become too computationally expensive. Luckily, usually only a subset of extreme (e.g. smallest or leftmost) eigenvalues are of interest, and these are computed by iterative algorithms based on multiplication of vectors by the matrix A of the problem on each iteration. The theoretically optimal approach is to compute on each iteration the best approximation to eigenvectors of interest in the so-called Krylov subspace, defined by some non-zero vector x and vectors y = A x, z = A y etc. The convergence of iterations depends on the distance between computed eigenvalues and the rest of the spectrum relative to the spectrum spread and may be too slow if this relative distance is small. One way to improve the convergence is to apply the same algorithm to the inverse of the matrix A - s I, where s is a scalar value near the eigenvalues of interest, and I is the identity matrix. Note that the inverse need not be computed explicitly, one just need to solve systems (A - s I)y = x etc. An algorithm of this kind is actually used (via an interface to a Fortran code) by MATLAB/SciPy function eigs.

For a multiple eigenvalue, eigs can only compute one eigenvector, and the same may happen for nearly multiple (poorly separated or 'clustered') eigenvalues as well. One way to avoid missing eigenvectors is to iterate several vectors simultaneously, i.e. to start with a matrix X with several columns instead of a single vector x and compute Y = A X etc. With sufficiently large number of columns in X, this block-iterative approach practically eliminates the risk of missing eigenvectors, while at the same time benefiting from highly optimized matrix-matrix multiplications. However, it obviously requires much more memory than the usual Krylov subspace iterations.

Krylov subspaces were originally used for solving symmetric linear systems of equations, and it turned out that the best approximation to the solution in these subspaces can be computed by a deceptively simple recursive procedure known as the Conjugate Gradient method. CG can also be applied to the eigenvalue computation, and although CG approximations in Krylov subspaces are no longer the best, they still are of comparable quality, and the convergence is remarkably good. It remains to note than block CG algorithms are implemented by SciPy package lobpcg and already mentioned package raleigh (the latter comes with usage examples demonstrating up to 60 times faster computation of eigenvalues of sufficiently large matrices compared to SciPy eigsh).

The already mentioned LOBPCG has many implementations. In MATLAB, including support for single precision, distributed or codistributed arrays, and tiling arrays, please see

https://www.mathworks.com/matlabcentral/fileexchange/48-locally-optimal-block-preconditioned-conjugate-gradient .

A plain C version is in https://github.com/lobpcg/blopex .

In other cases, LOBPCG is already included in the hosting package, e.g., Anasazi (Trilinos), SLEPc, hypre, SciPy, Octave, Julia, MAGMA, Pytorch, Rust, RAPIDS cuGraph and NVIDIA AMGX. For a comprehensive review, see https://en.wikipedia.org/wiki/LOBPCG

To specifically answer your question: " which method is the most efficient in the following situations: (a) Sparsely populated large matrices, and (b) Densely populated large matrices." more information is needed, such as

• the matrix is symmetric or not
• if the eigenvalue problem is generalized, i.e. Ax = lambda Bx
• how many eigen-pairs need to be computed and there the seeking eigenvalues are located.

For example, LOBPCG works only for symmetric problems, including generalized, to find