  Effective resistance, which originates from the field of circuits analysis,
is an important graph distance in spectral graph theory. It has found numerous
applications in various areas, such as graph data mining, spectral graph
sparsification, circuits simulation, etc. However, computing effective
resistances accurately can be intractable and we still lack efficient methods
for estimating effective resistances on large graphs. In this work, we propose
an efficient algorithm to compute effective resistances on general weighted
graphs, based on a sparse approximate inverse technique. Compared with a recent
competitor, the proposed algorithm shows several hundreds of speedups and also
one to two orders of magnitude improvement in the accuracy of results.
Incorporating the proposed algorithm with the graph sparsification based power
grid (PG) reduction framework, we develop a fast PG reduction method, which
achieves an average 6.4X speedup in the reduction time without loss of
reduction accuracy. In the applications of power grid transient analysis and DC
incremental analysis, the proposed method enables 1.7X and 2.5X speedup of
overall time compared to using the PG reduction based on accurate effective
resistances, without increase in the error of solution.
