Skip to content
Snippets Groups Projects
README.md 4.29 KiB
Newer Older
# 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
Tallulah Rytz's avatar
Tallulah Rytz committed
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);