A Practical Randomized GMRES Algorithm for Solving Linear Equation System in Circuit Simulation
Baiyu Chen, Jiawen Cheng, Wenjian Yu · 2025
Efficient solver for general linear equations is of significance for EDA problems. The generalized minimal residual (GMRES) method, which can solve general linear equations efficiently, is one of the most widely-used fundamental algorithms. Randomized Arnoldi process, which leverages sketched least-squares solver to orthogonalize Krylov subspace basis, has shown potential to promote the effectiveness of Arnoldi process, the core step in GMRES. However, how to make it more efficient, and utilize it to develop a practical GMRES solver is still an open problem. In this work, we aim at obtaining a practically-useful randomized GMRES algorithm (named PRGMRES) for solving general sparse linear equations. Firstly, an efficient estimator of residual error based on a modified randomized Gram-Schmidt process and a double-tolerance scheme are proposed to enable a practical restarted GMRES algorithm which terminates at a solution satisfying the specified accuracy tolerance. Then, a linear-time-complexity sketching algorithm based on Rademacher matrices is proposed to facilitate fast and robust random sketching. After that, incremental solution of the sketched least-squares problems, and the theoretical analysis supporting smaller sketching size are presented. Based on the above proposed techniques and theoretical results, the PRGMRES algorithm, which has stronger theoretically-supported stability and efficiency, is proposed. Numerical experiments on various circuit simulation problems validate the efficiency and effectiveness of the proposed algorithm.