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.
* 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
For normal matrix files, the file format is as follows -
- Line 1 will have the number of rows, then a tab space, then the number of columns
- 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 -
- Line 1 will have the number of rows, number of columns, and the number of non-zeros each separated by a tab-space
- 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
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.
Here's the expected output of the example solve in src/main.cpp
Here's an example interactive interface run:
