The fast power grid static analysis algorithm based on matrix reordering

With the rapid development of integrated circuit technology, the scale of power grid matrices is growing larger. Power grid analysis consistently presents formidable computational challenges, involving the solution of matrices with scales ranging from millions to even billions. Power grid analysis has also become one of the most time-consuming steps in chiplevel analysis. Therefore, efficient power grid analysis techniques are highly sought after for their capacity to conserve computational resources and expedite iteration speed. In this paper, leveraging the characteristics of power grid structures, we propose a text-based matrix reordering and decomposition technique. Through this approach, the original matrix of the power grid system can be seamlessly decomposed into two submatrices without compromising the integrity of the original matrix information. The submatrices can still maintain symmetric positive definiteness, enabling acceleration throughout the network solving process without altering the original solution. In contrast to current power grid hierarchical schemes, power grid decomposition technology, in order to ensure its computational accuracy, requires expensive costs to determine the boundary voltages and currents of the subgrid. The proposed technique exhibits wide applicability across various solvers, and we perform comparative analyses by selecting several representative solvers for static analysis of power grids. Experimental results demonstrate that this technique achieves nearly 100% speed improvement. For solvers lacking support for parallel computation, this approach represents an efficacious means of enhancing computational efficiency. Additionally, we observe that solvers designed for parallel acceleration can also achieve performance improvements exceeding 50%.