-
Tallulah Rytz authored5e59a472
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);