Solving SDD linear systems in nearly m log 1/2 n time

DOI10.1145/2591796.2591833zbMath1315.65026OpenAlexW2058706632MaRDI QIDQ5259568

Rasmus Kyng, Michael B. Cohen, Shen Chen Xu, Jakub W. Pachocki, Richard Peng, Gary Lee Miller, Anup B. Rao

Publication date: 26 June 2015

Published in: Proceedings of the forty-sixth annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/2591796.2591833

zbMATH Keywords

random matricestree embeddingscombinatorial preconditioningSDD linear systems

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Analysis of algorithms and problem complexity (68Q25) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random matrices (algebraic aspects) (15B52) Direct numerical methods for linear systems and matrix inversion (65F05) Preconditioners for iterative methods (65F08)

Related Items (27)

Randomized numerical linear algebra: Foundations and algorithms ⋮ A stochastic process on a network with connections to Laplacian systems of equations ⋮ Parametric Computation of Minimum-Cost Flows with Piecewise Quadratic Costs ⋮ Unnamed Item ⋮ Fitting a graph to one-dimensional data ⋮ A combinatorial cut-toggling algorithm for solving Laplacian linear systems ⋮ Optimization on the smallest eigenvalue of grounded Laplacian matrix via edge addition ⋮ The Expected Norm of a Sum of Independent Random Matrices: An Elementary Approach ⋮ Unnamed Item ⋮ Minimum cost flow in the CONGEST model ⋮ Decentralized Low-Stretch Trees via Low Diameter Graph Decompositions ⋮ Brief Announcement: Minimum Cost Maximum Flow in the CONGEST Model ⋮ Brief Announcement: The Laplacian Paradigm in Deterministic Congested Clique ⋮ Hardness Results for Structured Linear Systems ⋮ Unnamed Item ⋮ Using Petal-Decompositions to Build a Low Stretch Spanning Tree ⋮ Approximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis ⋮ A queueing network-based distributed Laplacian solver ⋮ Polynomial-time algorithms for submodular Laplacian systems ⋮ The game theoreticp-Laplacian and semi-supervised learning with few labels ⋮ Space Hardness of Solving Structured Linear Systems. ⋮ Local Flow Partitioning for Faster Edge Connectivity ⋮ Unnamed Item ⋮ A New Approach to Laplacian Solvers and Flow Problems ⋮ Solving Local Linear Systems with Boundary Conditions Using Heat Kernel Pagerank ⋮ Electrical flows over spanning trees ⋮ A fast algorithm for manifold learning by posing it as a symmetric diagonally dominant linear system

Uses Software

• SuLQ

Cites Work

• Unnamed Item
• Unnamed Item
• Efficient algorithms for privately releasing marginals via convex relaxations
• The Geometry of Differential Privacy: The Small Database and Approximate Cases
• Faster Algorithms for Privately Releasing Marginals
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Privately Releasing Conjunctions and the Statistical Query Barrier
• On the geometry of differential privacy
• Interactive privacy via the median mechanism
• The price of privately releasing contingency tables and the spectra of random matrices with correlated rows
• Lower Bounds in Differential Privacy
• Iterative Constructions and Private Data Release
• Characterizing the sample complexity of private learners
• Faster private release of marginals on small databases
• Bounds on the Sample Complexity for Private Learning and Private Data Release
• Differential Privacy and the Fat-Shattering Dimension of Linear Queries
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• New Efficient Attacks on Statistical Disclosure Control Mechanisms
• Collusion-secure fingerprinting for digital data
• On the complexity of differentially private data release
• Advances in Cryptology – CRYPTO 2004
• Answering n _{2+o(1)} counting queries with differential privacy is hard
• Theory of Cryptography

This page was built for publication: Solving SDD linear systems in nearly m log ^1/2 n time