Fast algorithms for IR drop analysis in large power grid

Research output: Chapter in book/report/conference proceedingConference proceedingpeer-review

106 Citations (Scopus)


Due to the extremely large size of power grids, IR drop analysis has become a computationally challenging problem both in terms of runtime and memory usage. Although IR drop analysis can be naturally formulated as the problem of solving a linear system, the system is too large to be solved by existing linear solvers. In this paper, we present two iterative algorithms based on node-by-node traversals and row-by-row traversals of the power grid, respectively. Our algorithms are extremely fast and guarantee convergence to the exact solutions. In fact, they can be considered as efficient implementations of the classical Successive Over Relaxation iterative method for solving linear systems. Our methods take full advantage of the special structure of the power grid. Experimental results show that our algorithms out-perform the Random-Walk-based algorithm which is the best known method today. For a 16-million node problem, our row-based algorithm took 26.47 minutes while the Random-Walk-based algorithm took 19.6 hours. Our row-based algorithm produced an exact solution while the Random Walk produced a solution with maximum error of 5.7 mV.

Original languageEnglish
Title of host publicationProceedings of the 2005 International Conference on Computer-Aided Design
Place of PublicationUnited States
Number of pages7
Publication statusPublished - Nov 2005
EventIEEE/ACM International Conference on Computer-Aided Design, ICCAD 2005 - San Jose, United States
Duration: 6 Nov 200510 Nov 2005 (Conference proceedings)


ConferenceIEEE/ACM International Conference on Computer-Aided Design, ICCAD 2005
Country/TerritoryUnited States
CitySan Jose
Internet address

Scopus Subject Areas

  • Software
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Fast algorithms for IR drop analysis in large power grid'. Together they form a unique fingerprint.

Cite this