{"ID":5438834,"CreatedAt":"2026-07-01T01:17:58.482524686Z","UpdatedAt":"2026-07-03T11:37:34.911515878Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.31535","arxiv_id":"2606.31535","title":"PEERS: A Parallel and Exact Effective Resistance Solver via Implicit Inversion and Augmented Symbolic Analysis","abstract":"High-precision effective resistance computation is a cornerstone of Electronic Design Automation (EDA) sign-off, yet it remains a fundamental bottleneck in large-scale power grid analysis, spectral sparsification, and circuit reliability. Existing approaches face a prohibitive \"precision-memory impasse\": approximate methods lack the stringent accuracy required for high-stakes industrial sign-off, while exact methods either suffer from redundant query overheads or trigger $O(n^2)$ memory explosions. To resolve this, we propose PEERS, a Parallel and Exact Effective Resistance Solver powered by an implicit inverse computing model of the Cholesky factor. By integrating a state-inherited augmented depth-first search (DFS) with a dynamic query update mechanism, PEERS eliminates numerical redundancy and evaluates all-edge resistance queries in a single parallel sweep. We provide a rigorous Work-Span analysis, proving that for graphs satisfying an $O(n^α)$ separator theorem, PEERS achieves a theoretically optimal parallel span of $O(n^α)$ while strictly maintaining $O(nnz(L))$ space complexity. Numerical evaluations on industrial benchmarks demonstrate that PEERS achieves an average speedup of 83.3x over state-of-the-art parallel solvers under identical memory constraints. Notably, PEERS processes a 1-million-node industrial graph in just 18.8 seconds and scales to 17 million nodes in under an hour, providing the first computationally feasible path for exact all-edge resistance analysis in multi-million-gate designs.","short_abstract":"High-precision effective resistance computation is a cornerstone of Electronic Design Automation (EDA) sign-off, yet it remains a fundamental bottleneck in large-scale power grid analysis, spectral sparsification, and circuit reliability. Existing approaches face a prohibitive \"precision-memory impasse\": approximate me...","url_abs":"https://arxiv.org/abs/2606.31535","url_pdf":"https://arxiv.org/pdf/2606.31535v1","authors":"[\"Baiyu Chen\",\"Lin Gan\",\"Guangwen Yang\",\"Wenjian Yu\"]","published":"2026-06-30T11:50:46Z","proceeding":"cs.AR","tasks":"[\"cs.AR\",\"cs.DC\",\"math.NA\"]","methods":"[]","has_code":false}