Linear System Solvers - Performance Comparison

A comprehensive C++ implementation and performance analysis of advanced linear system solving methods with sparse matrix support, iterative solvers, and preconditioners.

🎯 Quick Features Summary

Feature	Implementation	Performance Highlight
Direct Solvers	Gaussian Elimination, LU, Cholesky	Machine precision (10⁻¹²)
Iterative Solvers	Gauss-Seidel, Jacobi, SOR, CG	50× faster on large matrices
Sparse Matrices	CSR format	99.7% memory reduction
Preconditioners	Jacobi (diagonal)	Faster convergence
Matrix Analysis	Condition number, norms, properties	Stability insights
Memory Profiling	Peak usage tracking	Resource optimization
Exception Handling	Custom hierarchy with suggestions	Better debugging
Unit Tests	Google Test framework	100% pass rate

🖥️ Interactive GUI

NEW! Python GUI with real-time C++ solver integration:

# Install dependencies
pip install -r requirements.txt

# Launch GUI
python3 gui.py

Features:

• ✨ Matrix Input Grid - Easy matrix and vector entry
• 🎛️ Solver Selection - Choose from 4 different algorithms
• 📊 Real-time Visualization - Matrix heatmap & solution graphs
• ⚡ C++ Backend - Uses actual C++ solvers (not simulation)
• 📈 Performance Metrics - Execution time & residual error
• 🎨 Preset Matrices - Identity, Random, Diagonal dominant

📋 Overview

This project implements and benchmarks different algorithms for solving systems of linear equations Ax = b, comparing their:

• Execution time across different matrix sizes
• Accuracy (solution error)
• Scalability with increasing problem size

🎯 Implemented Algorithms

Direct Solvers

Algorithm	Complexity	Best Use Case	Advantages
Gaussian Elimination	O(n³)	Small-medium matrices	Partial pivoting, stable
LU Factorization	O(n³)	Multiple right-hand sides	Reusable decomposition
Cholesky	O(n³/6)	SPD matrices	2× faster than LU

Iterative Solvers

Algorithm	Complexity	Best Use Case	Convergence
Gauss-Seidel	O(kn²)	Large dense matrices	Faster than Jacobi
Jacobi	O(kn²)	Parallel computing	All updates independent
SOR	O(kn²)	Diagonal dominant	20-30% faster than GS
Conjugate Gradient	O(kn)	Sparse SPD matrices	Ultra-fast for sparse

Advanced Features

• Sparse Matrices: CSR (Compressed Sparse Row) format for 99%+ memory savings
• Preconditioners: Jacobi preconditioner for improved convergence
• Matrix Analysis: Condition number, matrix norms, diagonal dominance checking
• Memory Profiling: Track peak memory usage and compare dense vs sparse
• Exception Handling: Detailed error messages with troubleshooting suggestions

🛠️ Project Structure

optimization-and-search-cpp/
├── src/
│   ├── linear_solvers/
│   │   ├── gaussian_elimination.{h,cpp}        # Gaussian elimination with pivoting
│   │   ├── lu_factorization.{h,cpp}            # LU decomposition
│   │   ├── iterative_solver.{h,cpp}            # Gauss-Seidel & Jacobi
│   │   ├── sparse_iterative_solver.{h,cpp}     # Conjugate Gradient for sparse
│   │   ├── advanced_solvers.{h,cpp}            # SOR & Cholesky
│   │   └── preconditioner.{h,cpp}              # Jacobi preconditioner
│   ├── utils/
│   │   ├── matrix.{h,cpp}                      # Dense matrix operations
│   │   ├── sparse_matrix.{h,cpp}               # CSR sparse matrix
│   │   ├── matrix_analysis.{h,cpp}             # Condition number, norms
│   │   ├── memory_profiler.{h,cpp}             # Memory usage tracking
│   │   ├── timer.{h,cpp}                       # Performance timing
│   │   └── exceptions.h                        # Custom exception hierarchy
│   ├── main.cpp                                # Main benchmark driver
│   └── advanced_demo.cpp                       # Advanced features demo
├── tests/
│   ├── test_gaussian.cpp                       # Unit tests for direct solvers
│   ├── test_sparse.cpp                         # Unit tests for sparse matrices
│   ├── test_advanced.cpp                       # Unit tests for SOR/Cholesky
│   └── CMakeLists.txt                          # Test configuration
├── CMakeLists.txt                              # Main build configuration
├── Makefile                                    # Alternative build system
├── visualize.py                                # Python visualization script
├── benchmark_results.csv                       # Generated benchmark data
├── plots/                                      # Generated performance graphs
└── README.md

🚀 Building and Running

Prerequisites

• C++17 compatible compiler (GCC 7+, Clang 5+, MSVC 2017+)
• CMake 3.10+
• Google Test (for unit tests)
• Python 3.7+ (for visualization)
• Python packages: pandas, matplotlib, seaborn

Build Instructions

# Clone the repository
git clone https://github.com/Talha-Dmr/optimization-and-search-cpp.git
cd optimization-and-search-cpp

# Create build directory and compile
mkdir -p build
cd build
cmake ..
make

# Run the benchmark
./linear_solvers

# Run unit tests (optional)
ctest --output-on-failure

Using Makefile (Alternative)

# Build all targets
make

# Run advanced features demo
make demo

# Run main benchmark
make run

# Clean build artifacts
make clean

# Show available targets
make help

Generate Visualizations

# Install Python dependencies (if needed)
pip install pandas matplotlib seaborn

# Generate plots and analysis
python3 visualize.py

This will create:

• benchmark_results.csv - Raw benchmark data
• plots/ directory with performance graphs
• plots/summary_report.txt - Text summary of results

Run Advanced Features Demo

# Using Makefile
make demo

# Or directly
./build/advanced_demo

The demo showcases:

• Sparse matrix operations with CSR format
• Matrix analysis (condition number, norms)
• Memory profiling and comparison
• Performance benchmarks

📊 Benchmark Results

The program tests matrices of sizes: 10×10, 50×50, 100×100, 200×200, 500×500, 1000×1000

Key Findings

⏱️ Execution Time

• Small matrices (≤100): Direct methods are faster
• Large matrices (≥500): Iterative methods are ~10x faster
• Gauss-Seidel generally outperforms Jacobi in convergence speed

🎯 Accuracy

• Direct methods: Error ~10⁻¹² to 10⁻¹⁴ (machine precision)
• Iterative methods: Error ~10⁻⁸ (sufficient for most applications)
• All methods successfully solve the test systems

📈 Scalability

• Direct methods: Time grows as O(n³) - becomes slow for large n
• Iterative methods: Better scaling for large sparse matrices
• Performance gap increases dramatically with matrix size

Sample Performance (1000×1000 Diagonal Dominant Matrix)

Method	Time (ms)	Error	Speedup
Gaussian Elimination	843	3.8×10⁻¹¹	1×
LU Factorization	1094	1.4×10⁻¹¹	0.77×
Gauss-Seidel	17	1.1×10⁻⁸	50×
Jacobi	20	2.1×10⁻⁹	42×

Sparse Matrix Performance (1000×1000 Tridiagonal)

Metric	Sparse (CSR)	Dense	Advantage
Memory	54.66 KB	7.65 MB	99.3% savings
Storage	2,998 elements	1,000,000 elements	99.7% reduction
Solve Time (CG)	0.08 ms	N/A	Ultra-fast
Sparsity	99.70%	0%	Highly sparse

Actual benchmark results - Hardware may vary

📈 Generated Visualizations

The visualize.py script generates:

1. time_comparison_diagonal.png - Execution time vs matrix size (log-log plot)
2. time_comparison_random.png - Direct methods on random matrices
3. error_comparison.png - Solution accuracy comparison
4. speedup_comparison.png - Iterative methods speedup vs direct methods
5. bar_comparison.png - Bar charts for selected matrix sizes
6. summary_report.txt - Detailed statistical analysis

🧪 Test Matrices

Random Matrices

• Elements uniformly distributed in [1, 10]
• Tests general case performance
• Used for direct methods comparison

Diagonal Dominant Matrices

• Ensures convergence for iterative methods
• More representative of real-world sparse systems
• Condition: |a_ii| > Σ|a_ij| for all rows

💡 Key Insights & Recommendations

When to Use Each Method

Scenario	Recommended Method	Reason
Small matrices (n < 100)	Gaussian Elimination	Simple, fast, accurate
Multiple systems with same A	LU Factorization	Reuse decomposition
Large sparse matrices	Sparse CG	99% memory savings, ultra-fast
Large dense matrices	Gauss-Seidel	50× faster than direct
Parallel computing	Jacobi	Independent updates
High precision required	Direct methods	Machine precision (10⁻¹²)
Real-time applications	Iterative methods	Speed vs accuracy tradeoff
Memory-constrained	Sparse matrices	100× less memory
Tridiagonal systems	Sparse CG	Optimal performance

Performance Decision Tree

Matrix size?
├─ n < 100
│  └─ Use Gaussian Elimination (fast enough, accurate)
│
├─ 100 ≤ n < 500
│  ├─ Sparse? → Use Sparse Iterative (CG/Gauss-Seidel)
│  └─ Dense? → Use LU Factorization
│
└─ n ≥ 500
   ├─ Sparse? → **Use Sparse CG** (99% memory savings)
   ├─ Dense + Need Speed? → Use Gauss-Seidel (50× faster)
   └─ Dense + Need Precision? → Use LU (but slow)

Convergence Requirements for Iterative Methods

• Matrix must be diagonal dominant or symmetric positive definite
• Random matrices may not converge
• For general matrices, use preconditioners (advanced topic)

🔧 Customization

Adding More Matrix Sizes

Edit main.cpp line 168:

std::vector<size_t> sizes = {10, 50, 100, 200, 500, 1000, 2000};  // Add 2000

Adjusting Convergence Criteria

Modify in main.cpp when calling iterative solvers:

IterativeSolver::gaussSeidel(A, b, 1e-8, 5000);  // tolerance, max_iterations

Using Your Own Matrix

// In main.cpp
Matrix A(3, 3);
A(0,0) = 4; A(0,1) = -1; A(0,2) = 0;
A(1,0) = -1; A(1,1) = 4; A(1,2) = -1;
A(2,0) = 0; A(2,1) = -1; A(2,2) = 4;

std::vector<double> b = {15, 10, 10};

auto x = GaussianElimination::solve(A, b);
Matrix::printVector(x, "Solution");

🚀 Advanced Features

Sparse Matrix Support (CSR Format)

#include "utils/sparse_matrix.h"
#include "linear_solvers/sparse_iterative_solver.h"

// Create tridiagonal matrix
SparseMatrix A = SparseMatrix::tridiagonal(1000, 4.0, -1.0);
std::vector<double> b = /* ... */;

// Solve with Conjugate Gradient
auto x = SparseIterativeSolver::conjugateGradient(A, b, 1e-6, 1000);

// Memory savings: 99.7% for 1000×1000 tridiagonal

Matrix Analysis

#include "utils/matrix_analysis.h"

Matrix A = /* ... */;

// Comprehensive analysis
std::cout << MatrixAnalysis::analyze(A);

// Individual metrics
double cond = MatrixAnalysis::conditionNumber(A);
bool stable = MatrixAnalysis::isDiagonallyDominant(A);

Memory Profiling

#include "utils/memory_profiler.h"

MemoryProfiler profiler;
profiler.start();

// Your code here
Matrix A = Matrix::random(1000, 1000);

profiler.updatePeak();
size_t peak = profiler.stop();

std::cout << "Peak: " << MemoryProfiler::formatBytes(peak);

📚 Algorithm Details

Gaussian Elimination

1. Forward Elimination: Transform to upper triangular using row operations
2. Partial Pivoting: Swap rows to improve numerical stability
3. Back Substitution: Solve from bottom to top

LU Factorization

1. Decomposition: A = LU (Doolittle: L has 1s on diagonal)
2. Forward Substitution: Ly = b
3. Back Substitution: Ux = y

Gauss-Seidel

For each iteration:
  For i = 1 to n:
    x_i = (b_i - Σ(a_ij * x_j)) / a_ii
    (uses updated x values immediately)

Jacobi

For each iteration:
  For i = 1 to n:
    x_i_new = (b_i - Σ(a_ij * x_j_old)) / a_ii
    (uses only old x values)

🧪 Testing

The project includes comprehensive unit tests using Google Test framework:

# Build and run all tests
cd build
cmake ..
make
ctest --output-on-failure

# Run specific test suite
./test_gaussian      # Direct solver tests
./test_sparse        # Sparse matrix tests
./test_advanced      # SOR/Cholesky/preconditioner tests

Test Coverage:

• ✅ Gaussian Elimination (5 tests) - Simple systems, identity, diagonal dominant, error handling
• ✅ Sparse Matrices (4 tests) - Tridiagonal creation, multiplication, CG solver, memory efficiency
• ✅ Advanced Solvers (5 tests) - SOR convergence, Cholesky decomposition, preconditioners
• 100% pass rate across all test suites

🤝 How to Contribute

We welcome contributions! Here's how you can help:

Reporting Issues

• Use the GitHub Issues page
• Provide clear description, expected vs actual behavior
• Include system info (OS, compiler, CMake version)

Contributing Code

1. Fork the repository

   git clone https://github.com/YOUR_USERNAME/optimization-and-search-cpp.git
   cd optimization-and-search-cpp

2. Create a feature branch

   git checkout -b feature/your-feature-name

3. Make your changes

   • Follow existing code style (Google C++ Style Guide)
   • Add unit tests for new features
   • Update documentation (README, code comments)
   • Ensure all tests pass: ctest --output-on-failure

4. Commit and push

   git add .
   git commit -m "Add: brief description of your changes"
   git push origin feature/your-feature-name

5. Open a Pull Request

   • Describe what you've changed and why
   • Reference any related issues
   • Wait for code review

Areas We'd Love Help With

• 🚀 Performance: GPU acceleration (CUDA/OpenCL), SIMD optimizations
• 📊 Algorithms: QR decomposition, GMRES, BiCGSTAB
• 🧪 Testing: More edge cases, integration tests, benchmarks on different hardware
• 📖 Documentation: Tutorials, algorithm explanations, usage examples
• 🐛 Bug fixes: Check Issues

Code Style Guidelines

• Use meaningful variable names (condition_number not cn)
• Add comments for complex algorithms
• Keep functions focused (single responsibility)
• Follow const-correctness
• Use modern C++17 features where appropriate

🐛 Known Limitations

• Iterative methods require diagonal dominant or SPD matrices for convergence
• Single-threaded implementation (OpenMP parallelization planned)
• No pivoting in LU factorization (may fail on some matrices)
• Cholesky requires manual verification of SPD property

🔮 Future Enhancements

• OpenMP parallelization for large matrices
• GitHub Actions CI/CD pipeline
• Additional methods (QR, GMRES, BiCGSTAB)
• GPU acceleration (CUDA/OpenCL)
• Incomplete LU preconditioner
• Automatic SPD detection for Cholesky
• Python bindings (pybind11)

📝 References

• Golub, G. H., & Van Loan, C. F. (2013). Matrix Computations (4th ed.)
• Saad, Y. (2003). Iterative Methods for Sparse Linear Systems
• Press, W. H., et al. (2007). Numerical Recipes: The Art of Scientific Computing

📄 License

This project is open source and available under the MIT License.

👤 Author

Talha Demir

• GitHub: @Talha-Dmr

🙏 Acknowledgments

This project was developed as part of a numerical methods course to understand the practical performance characteristics of different linear system solvers.

---

⭐ If you find this project useful, please consider giving it a star!