Entrywise Approximate Solutions for SDDM Systems in Almost-Linear Time
Angelo Farfan, Mehrdad Ghadiri, Junzhao Yang
2026Year
Abstract
We present an algorithm that given any invertible symmetric diagonally dominant M-matrix (SDDM), i.e., a principal submatrix of a graph Laplacian, L and a nonnegative vector b, computes an entrywise approximation to the solution of L x = b in Õ(m no(1)) time with high probability, where m is the number of nonzero entries and n is the dimension of the system.
Ask about this paper
Your agent reads all of it.
Lune indexed this paper to the last equation, along with the top-tier papers that cite it. Ask a question and the answer quotes them.
Your agent calls
Luneget_paper_fulltext
Free to start. No credit card required.
Terminal
Install the CLIlune papers fulltext d4efe526-bd44-4647-94be-dcd8dfd7b7dcBuilds on2
Related papers
- Derandomizing Directed Random Walks in Almost-Linear TimeRasmus Kyng, Simon Meierhans, Maximilian ProbstFOCS 2022 · 5 citations
- Minor Sparsifiers and the Distributed Laplacian ParadigmSebastian Forster, Gramoz Goranci, Yang P. Liu, Richard Peng et al.FOCS 2021 · 12 citations
- Sparsified block elimination for directed laplaciansRichard Peng, Zhuoqing SongSTOC 2022 · 2 citations
- Structured Semidefinite Programming for Recovering Structured PreconditionersArun Jambulapati, Jerry Li, Christopher Musco, Kirankumar Shiragur et al.NeurIPS 2023 · 9 citations
- Breaking the Barrier of Self-Concordant Barriers: Faster Interior Point Methods for M-MatricesAdrian VladuSTOC 2025
