Parallel Gauss-Jordan Elimination and System Reduction for Efficient Circuit Simulation
For circuit simulation practitioners, this work offers incremental improvements in solving linear systems iteratively, but the methods are not broadly applicable beyond this specific domain.
The paper proposes two novel approaches to accelerate circuit simulation: a parallel Gauss-Jordan elimination algorithm and a partial system reduction method. Combined, they improve parallel efficiency on large matrices, achieving up to 1.5x speedup on the largest tested matrices.
For the purposes of electric circuit simulation, we consider an iterative simulation model based on solving systems of linear equations by Gauss-Jordan elimination (GJE) for individual moments in time. To accelerate the simulation, we propose two independent novel approaches: a parallel GJE algorithm and partial system reduction prior to the start of iterations. The former is based on a well-known strategy applied for the first time in this context, whereas the latter, to the best of our knowledge, proposes an entirely new system reduction approach. To evaluate performance, we implement these algorithms in C++ using OpenMP and run them on various input matrices. Our analyses of the individual methods show improved performance, whilst combining them maintains parallel efficiency after partial reduction on medium-sized matrices and even improves efficiency on the largest matrices on the tested machine.