Skip to content
Snippets Groups Projects

Readme

The purpose of this project is to implement a family of Power Methods as well as the QR method to calculate the real-valued eigenvalues of square real-valued dense and sparse matrices.

A family of Power Method classes are available:

  • Power Method
  • Inverse Power Method
  • Power Method with Shift
  • Inverse Power Method with Shift

The above classes have to ability to calculate the dominating eigenvalue (method dependent) of a matrix.

In addition, these classes can calculate all the eigenvalues of a matrix using deflation. However, these methods can be numerically unstable (especially for the Inverse Power Methods) and are not always recommended.

Instead, the QRMethod class should be used to calculate all the eigenvalues of a matrix.

[Warning] Currently, only dense and sparse matrices of type double from the eigen library are supported. However, allowing different scalar typed matrices in the future should be simple as most methods are templated

Compilation

In order to compile it you should first install googletest and eigen

git submodule update --init

Then, building is done as usual, e.g. with CLion/VSCode or in the terminal:

mkdir build
cd build
cmake ..
make

Running the Executable

After building the project, the executable will be located in the build/src folder. This executable demonstrates the usage of the implemented methods for both sparse and dense matrices.

By default, the matrix used for these examples is defined in the src/main.cpp file. You can modify this file to test the methods with different matrices.

To run the executable, use the following command in the terminal from the build directory:

./src/Eigenvalue

This will execute the program and display the results for the provided matrix.

Tests

We have provided some simple tests for our methods:

  • Diagonal 5x5
  • ⁠Triangular 5x5
  • ⁠Dense 5x5
  • ⁠Triangular 10x10
  • ⁠Diagonal sparse 5x5
  • ⁠Triangular sparse 10x10
  • ⁠Sparse 10x10
  • ⁠Exceeded Maximum allowed iterations

In order to run these tests, use CLion/VSCode or run the following lines in the command line:

ctest

Voici une version corrigée et améliorée de la section :

Documentation

In order to create the documentation, make sure to have doxygen installed, and run the following lines in the terminal:

cd documentation
doxygen

Examples

Given a dense (Eigen::MatrixXd A) or sparse (Eigen::SparseMatrix<double> A ) matrix A

PowerMethod

If you want to compute the dominant eigenvalue and all the eigenvalues of the matrix A using the Power Method, you can do the following:

PowerMethod power;
double largest_eigenvalue = power.FindDominantEigenvalue(A);
Eigen::VectorXd all_eigenvalues = power.FindEigenvalues(A);

You can also customize the tolerance and the maximum number of iterations allowed for the Power Method:

PowerMethod new_power(1e-5, 10);

InversePowerMethod

If you want to compute the smallest eigenvalue of a matrix A using the Inverse Power Method, you can do the following:

InversePowerMethod inversepower;
double smallest_eigenvalue = inversepower.FindSmallestEigenvalue(A);

Note: It is not recommended to use FindEigenvalues() with this method because it is unstable when deflating the matrix.

PowerMethodShift & InversePowerMethodShift

If you want to compute the eigenvalues of a matrix A using the Power Method with shift or the Inverse Power Method with shift, you can do the following:

PowerMethodShift  powershift(0.5); // Shift of 0.5
Eigen::VectorXd  all_evals =  powershift.FindEigenvalues(A);
double  shifted_eval =  inversepower.FindShiftedEigenvalue(A);

InversePowerMethodShift  inversepowershift;
double  inverse_shifted_eval =  inversepowershift.FindShiftedEigenvalue(A);

In addition, the shift can be adjusted to find different eigenvalues:

powershift.SetShift(1.5);
double  new_shifted_eval =  inversepower.FindShiftedEigenvalue(A);

QRMethod

If you want to compute all the eigenvalues of the matrix A using the QR Method, you can do the following:

QRMethod  qr;
Eigen::VectorXd  all_evals =  qr.FindEigenvalues(A);

You can also customize the tolerance and the maximum number of iterations allowed for the QR Method:

PowerMethod new_power(1e-5, 10);