Solving directed Laplacian systems in nearly-linear time through sparse LU factorizations

DOI10.1109/FOCS.2018.00089MaRDI QIDQ6944323zbMATH OpenFDO

Authors Aaron Sidford, Jonathan Kelner, Rasmus Kyng, Michael B. Cohen, Richard Peng, Anup B. Rao, John Peebles

Publication date 12 August 2025

Full work available at URL https://doi.org/10.1109/FOCS.2018.00089

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cited in

(9)

• Spectral sparsification via bounded-independence sampling
• Solving sparse linear systems faster than matrix multiplication
• Better sparsifiers for directed Eulerian graphs
• Diagonal of pseudoinverse of graph Laplacian: fast estimation and exact results
• Small-space spectral sparsification via bounded-independence sampling
• Directed capacity-preserving subgraphs: hardness and exact polynomial algorithms
• Optimal fine-grained hardness of approximation of linear equations
• Sparsification of directed graphs via cut balance
• Pseudodistributions that beat all pseudorandom generators

This page was built for publication: Solving directed Laplacian systems in nearly-linear time through sparse LU factorizations

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