Linear Equations Solver in C++
> High-Performance Numerical Linear Algebra Engine in C++ with OpenMP Multithreading & Cache-Conscious Memory Architecture
A high-performance numerical computing engine developed in modern C++ to solve large-scale systems of linear equations using Gaussian elimination with partial pivoting. Designed to tackle extreme computational workloads, the engine features an interactive CLI REPL, an automated equation generator for synthetic benchmarks, and parallelized elimination pipelines. Solves massive systems up to 10,000 equations in ~3 minutes through aggressive algorithmic and hardware-level optimizations.
Low-level system architecture designed around hardware efficiency and cache locality. Implements a dense row-major matrix stored as a contiguous 1D memory buffer, eliminating pointer-chasing overhead and maximizing CPU L1/L2/L3 cache line utilization during row elimination.
Interactive command-line interface allowing users to manually enter linear equations, inspect matrix coefficients, solve systems step-by-step, and query solutions.
Automated generation mode capable of streaming massive dense systems to test CPU execution times, memory throughput, and algorithmic efficiency under varying matrix dimensions.
Multi-threaded execution engine utilizing OpenMP compiler pragmas for parallel row elimination across all available CPU cores.
When scaling to thousands of equations, processor speed vastly outpaced the memory bus bandwidth (the classic Memory Wall). Traditional 2D dynamic arrays (vector<vector<double>> or double**) caused frequent cache misses, pointer indirection, and memory bus saturation.
Flattened the entire 2D matrix into a single contiguous 1D memory buffer (index = row * cols + col). This guaranteed sequential spatial cache locality, allowing hardware prefetchers to load cache lines continuously into L1/L2 caches without memory stall cycles.
In parallelizing Gaussian elimination, naive row distribution across threads introduced thread contention, cache coherence invalidations (false sharing), and excessive synchronization barrier overhead.
Parallelized only the computationally intensive independent row-elimination loops using dynamic OpenMP scheduling while keeping pivot selection and row swapping synchronous, minimizing thread lock contention.
Standard Gaussian elimination accumulates catastrophic round-off errors and division-by-near-zero instability on large dense matrices.
Implemented partial pivoting by dynamically scanning each column for the maximum absolute value pivot element and swapping rows prior to elimination, preserving double-precision floating-point accuracy.