Advancing General Sparse Linear-Equation Solvers via Nested-Dissection-Based Parallel Scheduling and Randomized Linear Algebra

Sparse linear-equation solvers are indispensable to circuit simulation. They provide the mathematical engine that faithfully forecasts the dynamic response of analog circuits. In this invited paper, we present two novel techniques to speed up these solvers. The first is a parallel LU factorization driven by a new task scheduling strategy. Based on the nested dissection approach for matrix reordering, we derive a task assignment/scheduling strategy which largely reduces synchronization and develops more parallelism. Thus, a more efficient parallel sparse LU factorization algorithm (named SubtreeLU) is obtained. It outperforms both PARDISO and CKTSO in computational speed while remaining similar robustness. The second technique is a practical randomized GMRES algorithm. By implementing the Gram-Schmidt process with an extremely efficient random sketched linear-least-squares kernel, we obtain a fast randomized Arnoldi procedure that orthogonormalizes the Krylov subspace basis. Coupled with on-the-fly residual error estimates, this yields a practical randomized GMRES that is provably stable and runs remarkably faster than the standard GMRES on a wide range of circuit and field simulation benchmarks.