SimpleQRAlgorithm

SimpleQRAlgorithm is a C# implementation of the QR algorithm for finding the eigenvalues and eigenvectors of a real square matrix.

Background

The QR Algorithm is a numerically stable algorithm which uses QR decompositions to diagonalize any real square matrix. When running the QR Algorithm on a matrix for iterations, the Gram-Schmidt process is used to decompose the matrix into two components and , such that . Then, for some iterations, .

So, in essence, at each iteration the QR Algorithm decomposes the previously obtained matrix into the and components. It then calculates the product between and to obtain the new matrix. Eventually the algorithm converges and the eigenvalues of the original matrix can be found on the diagonal of the resulting matrix . The columns of the matrix represent the corresponding eigenvectors. To verify the result, the original matrix can be reconstructed from the decomposition .

Eigenvalue algorithms have many applications. For instance, it can be used to calculate the square root of a real square matrix . In this case, the matrix can be decomposed using the QR algorithm into , where is the matrix with eigenvectors as columns and is the diagonal matrix with the eigenvalues on the diagonal. The square root is then given by , where is the matrix with the square root of the eigenvalues on the diagonal.

Setup

SimpleQRAlgorithm has no dependencies as it comes with a small linear algebra library, so using it in your project is simple:

1. Clone this repository into your project
2. Import SimpleQRAlgorithm in your project
3. Run the algorithm on any real square matrix

Example

The following example shows how to run the algorithm on a matrix.

// The matrix to run the algorithm on.
float[,] matrix = {
    {1, 2, 3},
    {2, 3, 5},
    {3, 5, 6}
};

// The number of iterations the algorithm should run for.
int numberOfIterations = 10;

// Run the algorithm on the matrix and
// output the matrix' eigenvalues and eigenvectors.
QRAlgorithm.Diagonalize(
    matrix, 
    numberOfIterations, 
    out float[,] eigenvalues, 
    out float[,] eigenvectors
);

Support

If you encounter any bugs, please create an issue with a description and the steps to reproduce the bug on the issues board.