Group Lads

Group members - Nikhil Kumar, Ben Walsh, Akhil Mohan

Matrix Library

This project describes a library that can be used to solve linear systems (Ax=b). The source code is mainly contained in the Matrix.h and Matrix.cpp files, with an example in main.cpp. Sparse matrices are implemented in CSRMatrix.h / CSRMatrix.cpp. Code relating to the user interface is contained in Interface.h / Interface.cpp.

We started by writing a Jacobi solver for dense matrices, followed by a Cholesky solver for dense matrices. The latter involved implementing a triangular solve. We then implemented the CSR Matrix class, with its own triangular solver. We then added 2 iterative solvers for it. More information on the solver methods and development process can be found in the Project Report.

Functionality implemented

* Github workflow actions to compile and run the test suite and benchmarks on a remote Linux system
* Reading / Writing Dense and Sparse Matrices to file
* Printing the matrix to stdout and printing values (1D) to stdout
* Storing a sparse matrix in CSR (Compressed Sparse Row) form, and modifying it
* Solving a dense system with a Symmetric Positive-Definite Matrix (SPD) using a Cholesky Decomposition
* Solving a dense system with an iterative Jacobi method
* Solving a sparse (CSR) triangular system with dense RHS vector (b)
* Solving a sparse (CSR) upper triangular system with sparse RHS vector (b)
* Solving a diagonally dominant sparse system with an iterative Jacobi method
* Solving a sparse Symmetric Positive-Definite (SPD) system with an iterative Krylov Subspace Method (Conjugate Gradient)
* Working interface to allow a user to solve a dense or sparse linear system

Matrix File Formats

For normal matrix files, the file format is as follows -

1. Line 1 will have the number of rows, then a tab space, then the number of columns
2. Line 2 will have the tab-spaced values of each entry in row-major format, i.e all elements of row 0 before any elements of row 1

For example,

    [ 1  2   3  4 ]
A = [ 5  6   7  8 ]
    [ 9  10  11 12 ]
    [ 13 14  15 16 ]

would look like

For CSR matrix files, the format is as follows -

1. Line 1 will have the number of rows, number of columns, and the number of non-zeros each separated by a tab-space
2. Line 2 -> nnz+1 will have 3 values, the row index, the column index, and the data value at that index

For example a sparse matrix,

    [ 1  0  3 ]
A = [ 0  2  0 ]
    [ 0  0  4 ]

would look like

Compiling and Running

The code can be compiled from the top-level directory by executing

make

This will compile the executable in src/main.cpp and deposit an executable named main in the bin/ directory. You can then run the executable by typing

bin/main

This file shows an example solve using some of the many matrices provided in our data/ directory. To use the interactive user interface, run

make interactive

bin/ladsSolve

To run the test suite, type

make test

and it will compile the test suite automatically. test1 is for dense matrix functionality, test2 for sparse matrix functionality, and test3 for interface functionality.

To run a benchmark test on your system, run

make benchmark

bin/benchmark

The benchmarks are run on large matrices generated by a somewhat documented Python script, found in the tools/ directory of the repository.

Demonstrations

Here's the expected output of the example solve in src/main.cpp

Here's an example interactive interface run: