93 citations · 537 across the 73 of their papers we have counts for
7 papers · 1 filter
Solving Directed Laplacian Systems in Nearly-Linear Time through Sparse LU Factorizations
Michael B. Cohen, Jonathan Kelner, Rasmus Kyng +4
We show how to solve directed Laplacian systems in nearly-linear time. Given a linear system in an Eulerian directed Laplacian with nonzero entries, we show how to…
Constant Arboricity Spectral Sparsifiers
Timothy Chu, Michael B. Cohen, Jakub W. Pachocki +1
We show that every graph is spectrally similar to the union of a constant number of forests. Moreover, we show that Spielman-Srivastava sparsifiers are the union of O(logn) forests…
Graph Sparsification, Spectral Sketches, and Faster Resistance Computation, via Short Cycle Decompositions
Timothy Chu, Yu Gao, Richard Peng +3
We develop a framework for graph sparsification and sketching, based on a new tool, short cycle decomposition -- a decomposition of an unweighted graph into an edge-disjoint collec…
Incomplete Nested Dissection
Rasmus Kyng, Richard Peng, Robert Schwieterman +1
We present an asymptotically faster algorithm for solving linear systems in well-structured 3-dimensional truss stiffness matrices. These linear systems arise from linear elasticit…
Graph Sketching Against Adaptive Adversaries Applied to the Minimum Degree Algorithm
Matthew Fahrbach, Gary L. Miller, Richard Peng +3
Motivated by the study of matrix elimination orderings in combinatorial scientific computing, we utilize graph sketching and local sampling to give a data structure that provides a…
Fully Dynamic Effective Resistances
David Durfee, Yu Gao, Gramoz Goranci +1
In this paper we consider the \emph{fully-dynamic} All-Pairs Effective Resistance problem, where the goal is to maintain effective resistances on a graph among any pair of quer…