Due to the positive feedback loop between power grid Joule heating and the linear temperature dependence of resistivity, non-uniform temperature profiles on the power grid in high-performance IC influence the IR drop in the power grid. Lack of accurate evaluation of thermal effect on the IR drop in the power grid may lead to over-design; or worse, underestimates the IR drop due to increased local temperature. This paper presents a method to compute the temperature-dependent IR drop on the power grid extremely fast. We propose a novel thermal model and a mathematical formulation to compute the temperature profiles on the power grid efficiently. Compared to the traditional thermal lumped model, which gives a much larger thermal network than the original power grid (20 times more nodes), our model takes advantage of power grid properties, and reduces the size of the thermal equivalent network dramatically (only 13% of the size of the power grid). Iterative methods are used to efficiently update the IR drops based on the new temperature profile. Experimental results show that without considering temperature impact, the worst IR drop analysis can have error up to 10%.