Determinant-Preserving Sparsification of SDDM Matrices
From MaRDI portal
Publication:5117381
DOI10.1137/18M1165979zbMath1451.68200OpenAlexW3011465071MaRDI QIDQ5117381
David Durfee, Richard Peng, John Peebles, Anup B. Rao
Publication date: 25 August 2020
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/18m1165979
Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Approximation algorithms (68W25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)
Related Items
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Local characteristics, entropy and limit theorems for spanning trees and domino tilings via transfer-impedances
- User-friendly tail bounds for sums of random matrices
- The complexity of partial derivatives
- A randomized algorithm for approximating the log determinant of a symmetric positive definite matrix
- Generating Random Spanning Trees via Fast Matrix Multiplication
- Probability on Trees and Networks
- Nearly Linear Time Algorithms for Preconditioning and Solving Symmetric, Diagonally Dominant Linear Systems
- L p Row Sampling by Lewis Weights
- Maintaining information in fully dynamic trees with top trees
- Spectral Sparsification of Graphs
- The Random Walk Construction of Uniform Spanning Trees and Uniform Labelled Trees
- Generating random combinatorial objects
- Random spanning tree
- Self-adjusting binary search trees
- The Numbers of Spanning Trees, Hamilton Cycles and Perfect Matchings in a Random Graph
- Sparsification—a technique for speeding up dynamic graph algorithms
- Nearly Tight Oblivious Subspace Embeddings by Trace Inequalities
- Unranking and ranking spanning trees of a graph
- Two Algorithms for Unranking Arborescences
- Almost-linear-time algorithms for Markov chains and new spectral primitives for directed graphs
- Sampling random spanning trees faster than matrix multiplication
- Faster Generation of Random Spanning Trees
- An almost-linear time algorithm for uniform random spanning tree generation
- An efficient parallel solver for SDD linear systems
- Sparsified Cholesky and multigrid solvers for connection laplacians
- Fast Generation of Random Spanning Trees and the Effective Resistance Metric
- Lx = b
- Multiplying matrices faster than coppersmith-winograd
- A general framework for graph sparsification
- Graph Sparsification by Effective Resistances
