# Linear algebra system of equation solver

The linear algebra system of equation solver library provides a lightweight implementation of the Conjugate Gradient (CG) algorithm to iteratively solve the linear system of the form \f$\mathbf{Ax}=\mathbf{b}\f$. It is particularly well suited to solving partial differential equations for CFD applications using an implicit discretisation. 

## Introduction
Solving the linear system of equations in the form of \f$\mathbf{Ax}=\mathbf{b}\f$ can be achieved with a simple Gauss elimination. However, for large coefficients matrices \f$\mathbf{A}\f$, such as occurring in CFD applications, inverting the original matrix \f$\mathbf{A}\f$ is not practical. Instead, an approximate procedure can be used which produces results much faster compared to a direct inversion of the matrix.

Furthermore, the coefficient matrix \f$\mathbf{A}\f$ is typically sparse, where most elements are zero. Storing the entire matrix would result in wasted storage and, in fact, in most cases, is not possible. Solving the system of the form \f$\mathbf{Ax}=\mathbf{b}\f$ requires an efficient matrix storage solution, which is commonly achieved by the compressed spare row (CSR)[^1] matrix storage format.

The CSR matrix is efficient in the storage of data but more complicated in terms of inserting elements into the matrix. Since inserting and retrieving data can be somewhat more challenging, a dedicated vector class is also required to achieve an efficient matrix-vector multiplication.

Both of these classes are then used by a solver class which provides a base class to implement iterative solvers, for which one such implementation is provided in the form of the Conjugate Gradient (CG) algorithm. While this is the only provided algorithm, the matrix and vector class are general enough to allow for easy extension of the library by providing a dedicated solver class implementation. 

## Installation

The library ships with a CMake-based installation file, that can be used to compile and install the library either as a static or shared (dynamic) library across different platforms. It uses Conan as the package manager to get all required dependencies into the project (here, Doxygen for creating the documentation, and Gtest for running the tests, both dependencies are optional).

All source code is provided within the `linearAlgebraLib` folder. In order to test that the library is working correctly, the compilation can be tested with a few tests that are provided in the `tests` folder. In particular, we have unit, integration, and system tests provided in `tests/unit`, `tests/integration`, and `tests/system`, respectively. We use CTest to execute all tests after successful compilation.

### Check system requirements

First, we will need to ensure that the minimum requirements are satisfied. We need CMake (minimum version 3.23), Python (version 3.X), and a C++ compiler.

We can check that we have these installed by typing

```bash
# check cmake
cmake --version

# check python (Linux, macOS)
python3 --version

# check python (windows)
py --version

# check compiler (Linux)
g++ --version

# check compiler (macOS)
clang++ --version

# check compiler (windows)
cl.exe
```

If all of these return a version and no error message we are ready to go.

### Installing dependencies

We use the Conan package manager to install all of our dependencies. If you have not installed it yet, you can check out [this guide](https://cfd.university/learn/automating-cfd-solver-and-library-compilation-using-cmake/how-to-add-external-libraries-into-your-cfd-solver-using-cmake#aioseo-the-preferred-way-using-a-package-manager) to get it installed and set up. Once you have Conan installed and a sensible profile available, you can install all required packages using the following command:

```bash
conan install . -pr dev --output-folder=build --build=missing
```

Where I am using my ```dev``` profile, though you can omit this if you just want to install everything using your default profile. To make Doxygen available, we have to source the environmental variables for Conan, which are located in the ```build/``` folder. To do so, change into the ```build/``` and then execute the following

```bash
# UNIX
./conanbuild.sh

# Windows
.\conanbuild.ps1
```

Conan does not generate PowerShell (```*.ps1```) files by default, but the above-linked article will show how this can be requested within the profile settings.

### Compiling the project

Next, we can compile the project from within the ```build/``` folder. The following command builds the library as a shared (dynamic) library, along with documentation and tests:

```bash
cmake -DCMAKE_BUILD_TYPE=Debug -DCMAKE_TOOLCHAIN_FILE="conan_toolchain.cmake" -DBUILD_DOCS=ON -DENABLE_SHARED=ON -DENABLE_TESTS=ON -G Ninja ..
```

The build-type is set to Debug, and we are using the ```conan_toolchain.cmake``` file that was generated by Conan. I am also using the ```Ninja``` build tool, but if you want to use your native build tool, you can omit the ```-G Ninja``` CMake flag.

With the project configured, we are now in a position to compile the project using

```bash
cmake --build . --config Debug
```

Finally, if we want to install it to a specific directory on our system, we can add an install step

```bash
cmake --install . --prefix C:\temp --config Debug
```

where the ```--prefix``` determines the location where the library and documentation should be installed to.

We can also create the graphical installer if we want, which requires the Qt installer framework (IFW). You can find [installation instructions here](https://cfd.university/learn/automating-cfd-solver-and-library-compilation-using-cmake/how-to-use-cmake-cpack-to-create-beautiful-gui-installers#aioseo-getting-the-qt-install-framework). If this is installed, then creating the installer is as simple as typing

```bash
cpack
```

If we request to build the tests along with the project, then we can use CTest to check that all tests are passing as expected:

```bash
ctest
```

## Usage

The following shows how to work with the different classes. This is a lightweight library and if you know how to create a vector, a matrix, and a linear algebra solver instance, you know all there is to work with this library. 

### Creating a matrix {#useMatrix}

The following example shows how to create a matrix and use it:

```cpp
#include <iostream>
#include "linearAlgebraLib/linearAlgebraLib.hpp"

int main() {
  // create a matrix with 3 rows and 3 columns
  linearAlgebraLib::SparseMatrixCSR matrix(3, 3);

  // set value for the first row, and second column to 1.8
  matrix.set(1, 2, 1.8);

  // get the value for the first row and second column
  auto value = matrix.get(1, 2);

  // print the entire matrix to the console
  std::cout << matrix << std::endl;

  return 0;
}
```

### Creating a vector {#useVector}

The following example shows how to create a vector and use it:

```cpp
#include <iostream>
#include "linearAlgebraLib/linearAlgebraLib.hpp"

int main() {
  // create a vector with 3 entries
  linearAlgebraLib::Vector vector(3);

  // set data
  vector[0] = 1.2;
  vector[2] = -7.1;

  // get individual components
  auto v0 = vector[0];

  // calculate L2 norm of vector
  auto l2norm = vector.getL2Norm();

  // play around with arithmetic operations
  linearAlgebraLib::Vector v1(3);
  linearAlgebraLib::Vector v2(3);

  // set vectors if you like, skipped here ...

  auto addition = v1 + v2;
  auto subtraction = v1 - v2;
  auto dotProduct = v1.transpose() * v2;
  auto scalarMultiplication = 2.0 * v1;

  // print content of vector to the console
  std::cout << vector << std::endl;

  // create vector and matrix for matrix-vector product
  linearAlgebraLib::Vector vector(3);
  linearAlgebraLib::SparseMatrixCSR matrix(3, 3);

  // set vector and matrix if you like, skipped here ...

  auto resultVector = matrix * vector;

  return 0;
}
```

### Creating a linear system of equations {#useSolver}

The following example shows how to create a linear solver instance and use it:

```cpp
#include <iostream>
#include "linearAlgebraLib/linearAlgebraLib.hpp"

int main() {
  // define how many cells are being used, i.e. mesh size
  unsigned numberOfCells = 1000;

  // create vector and matrix for linear algebra solver, we'll use the notation Ax=b here
  linearAlgebraLib::Vector b(numberOfCells);
  linearAlgebraLib::SparseMatrixCSR A(numberOfCells, numberOfCells);

  // set vector and matrix if you like, skipped here ...
  
  // create conjugate gradient linear solver
  linearAlgebraLib::ConjugateGradient solver(numberOfCells);

  // set coefficient matrix and right-hand side vector in linear system  
  solver.setRightHandSide(b);
  solver.setCoefficientMatrix(A);

  // solve the linear system, using 100 iterations at most and a convergence threshold of 1e-12
  linearAlgebraLib::Vector x = solver.solve(100, 1e-12);

  // if we computed A * x now, this should result in b.
  auto b_calculated = A * x;

  // we can check now that b and b_calculated are the same ...

  return 0;
}
```

## References
[^1]: [Matt Eding - Sparse Matrices](https://matteding.github.io/2019/04/25/sparse-matrices/)