Parallel_Linear_Solver

• Modern C++ Software which uses OpenMP to parallelise the three classic Algebraic Iterative Methods: Jacobi, Gauss-Seidel and Successive Over Relaxation (SOR) for solving Systems of the form Ax = b.
• Note: this software looks at measuring convergence of the solvers and not on solving a large algebraic system of equations; another time.

TODO

• Experiment with a range of relaxation factors.

Introduction

• There is a problem in trying to parallelise the Gauss-Seidel & SOR methods because they are inherently sequential due to the dependency on the latest updated values within each iteration.
• However, we can parallelise it partially using a Red-Black Ordering Scheme.
• However, this scheme is more appropriate for systems where the matrix isn't dense.
• If the matrix is dense, true parallel forms of the methods is tricky, and so the algorithm logic has to be altered.
• If the matrix is dense, we can use Graph Colouring (AKA Multi-Colouring).
• Note: range-based for loops are used in places, so a compiler which supports C++20 features is required. However, OpenMP still requires traditional (index-based) for loops.

The Iterative Solvers

• Here is a brief overview of the methods.

The Jacobi Method

• TODO.

The Gauss-Seidel Method

• TODO.

The Successive Over Relaxation (SOR) MethodUpdate laPSolver.cpp

• TODO.

Red-Black Ordering Scheme: What is it?

• This is a technique to organize a structured grid (like a 2D matrix) into two independent groups of points — typically labeled "red" and "black" like a chessboard pattern.
• Points of one colour can be updated in parallel because none of them directly depend on each other - only on the other colour's points.
• You alternate updating all the red points and then all the black points in each iteration.

Requirements

• Compiler:g++ 13.1.0.
• OS: Ubuntu 20.04.
• OpenMP. For parallelising the iterative methods: Jacobi, Gauss-Seidel and SOR.
• CMake. For building the software.
• matplotlib-cpp. For plotting Convergence Rates.

Instructions for getting and Running the Software

• $ git clone git@github.com:MRLintern/Parallel_Linear_Solver.git
• $ cd Parallel_Linear_Solver
• $ mkdir build -p && cd build
• $ cmake ..
• $ cmake --build .
• $ ./laPSolver
• The .csv files are saved in a folder called Results (within build).

Results

• A Python script called plotter.py is provided to plot the results. This can be found in the Results folder.
• A sample of the results is provided; go to the Results directory. You'll find a collated data set and a data set for each algorithm.
• At present this plots the collated data set.