Power grid analysis using random walks

This paper presents a linear-time algorithm for the DC analysis of a power grid, based on a random walk technique. Experimental results show that the proposed method is faster than existing approaches and has an acceptable error margin. It also has a desirable property of localizing computation, and can be extended to RCnetwork transient analysis. This method has been applied to circuits of up to 70K nodes, for which the solution time for a single node was 0.42 sec and the complete solution was obtained in 17.6 sec. 1