An Aggregation-based Algebraic Multigrid Method for Power Grid Analysis

Yu-Min Lee,  Huan-Yu Chou,  Pei-Yu Huang
National Chiao-Tung University, Taiwan


This paper develops an aggregation-based algebraic multigrid (AbAMG) method to efficiently analyze the power delivery network. Different from the conventional algebraic multigrid (AMG) scheme, an innovative constructing method of global inter-grid mapping operator is employed to not only enhance the sparsity of coarse grid operator for reducing the computational complexity but also solve the problem with better convergent rate. The proposed method can solve the circuit with size over two millions in 167.6 CPU seconds (including DC analysis, and transient analysis with 50 time steps), and the maximum error is less than 1%. The significant runtime improvement, over 26X faster than the InductWise, over 2X faster than the IEKS method and over 1.25X faster than traditional AMG, and less memory usage, 40% of the memory usage in InductWise and half of the memory usage in IEKS, are demonstrated. Experimental results show that this AbAMG solver is very efficient in both runtime and memory usage.