An efficient parallel solver for SDD linear systems
From MaRDI portal
Abstract: We present the first parallel algorithm for solving systems of linear equations in symmetric, diagonally dominant (SDD) matrices that runs in polylogarithmic time and nearly-linear work. The heart of our algorithm is a construction of a sparse approximate inverse chain for the input matrix: a sequence of sparse matrices whose product approximates its inverse. Whereas other fast algorithms for solving systems of equations in SDD matrices exploit low-stretch spanning trees, our algorithm only requires spectral graph sparsifiers.
Recommendations
- A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
- Approaching optimality for solving SDD linear systems
- Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
- Solving SDD linear systems in nearly \(m \log^{1/2} n\) time
- Nearly linear time algorithms for preconditioning and solving symmetric, diagonally dominant linear systems
Cites work
- Advances in Cryptology – CRYPTO 2004
- Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
- Bounds on the sample complexity for private learning and private data release
- Characterizing the sample complexity of private learners
- Collusion-secure fingerprinting for digital data
- Differential privacy and the fat-shattering dimension of linear queries
- Efficient algorithms for privately releasing marginals via convex relaxations
- Faster algorithms for privately releasing marginals
- Faster private release of marginals on small databases
- scientific article; zbMATH DE number 5485440 (Why is no real title available?)
- scientific article; zbMATH DE number 5485574 (Why is no real title available?)
- Interactive privacy via the median mechanism
- Iterative Constructions and Private Data Release
- Lower bounds in differential privacy
- New Efficient Attacks on Statistical Disclosure Control Mechanisms
- On the complexity of differentially private data release, efficient algorithms and hardness results
- On the geometry of differential privacy
- Our Data, Ourselves: Privacy Via Distributed Noise Generation
- Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
- The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
- Theory of Cryptography
Cited in
(38)- Efficient approximate solution of sparse linear systems
- Engineering a combinatorial Laplacian solver: lessons learned
- A queueing network-based distributed Laplacian solver
- Unified frameworks for high order Newton-Schulz and Richardson iterations: a computationally efficient toolkit for convergence rate improvement
- A linear work, \(O(n^{1/6})\) time, parallel algorithm for solving planar Laplacians
- Constructing linear-sized spectral sparsification in almost-linear time
- A new approach to Laplacian solvers and flow problems
- Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
- Solving local linear systems with boundary conditions using heat kernel pagerank
- Density independent algorithms for sparsifying k-step random walks
- Probabilistic logarithmic-space algorithms for Laplacian solvers
- Sparse approximations with interior point methods
- Parallelizable Global Quasi-Conformal Parameterization of Multiply Connected Surfaces via Partial Welding
- scientific article; zbMATH DE number 7561283 (Why is no real title available?)
- Derandomization beyond connectivity: undirected Laplacian systems in nearly logarithmic space
- Hardness results for structured linear systems
- Determinant-preserving sparsification of SDDM matrices
- Parallelizable global conformal parameterization of simply-connected surfaces via partial welding
- Solving SDD linear systems in nearly \(m \log^{1/2} n\) time
- An approximate algorithm to solve linear systems by matrix with off-diagonal exponential decay entries
- Approaching optimality for solving SDD linear systems
- A simple, combinatorial algorithm for solving SDD systems in nearly-linear time
- Approximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis
- scientific article; zbMATH DE number 7650109 (Why is no real title available?)
- A combinatorial cut-toggling algorithm for solving Laplacian linear systems
- Almost universally optimal distributed Laplacian solvers via low-congestion shortcuts
- Graph Sparsification, Spectral Sketches, and Faster Resistance Computation via Short Cycle Decompositions
- Minimum cost flow in the CONGEST model
- Brief Announcement: Minimum Cost Maximum Flow in the CONGEST Model
- Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique
- Spectral sparsification via bounded-independence sampling
- Better sparsifiers for directed Eulerian graphs
- Electrical flows for polylogarithmic competitive oblivious routing
- A simpler and parallelizable \(O(\sqrt{\log n})\)-approximation algorithm for \textsc{Sparsest Cut}
- Ultrasparse ultrasparsifiers and faster Laplacian system solvers
- Small-space spectral sparsification via bounded-independence sampling
- Almost-linear-time weighted _p-norm solvers in slightly dense graphs via sparsification
- AC(k): robust solution of Laplacian equations by randomized approximate Cholesky factorization
This page was built for publication: An efficient parallel solver for SDD linear systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5259567)
