Computing Effective Resistances on Large Graphs Based on Approximate Inverse of Cholesky Factor

arXiv2303.03617MaRDI QIDQ6428612FDOQ6428612

Publication date: 6 March 2023

Abstract: 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.

This page was built for publication: Computing Effective Resistances on Large Graphs Based on Approximate Inverse of Cholesky Factor

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6428612)