Spectral graph sparsification Part 2: [An O(mlog^2 n) algorithm for solving SDD systems]

Channel:
Microsoft Research
Subscribers:
344,000
Published on ● Video Link: https://www.youtube.com/watch?v=_SSHyP4_-Sw


Category:
Vlog
Duration: 1:03:28
90 views
1

We present the fastest known algorithm for solving symmetric diagonally dominant (SDD) systems. If the number of the non-zeros in the system matrix is m, and the desired error is err, the algorithm runs in time O(mlog^2 m log(1/err) ). The heart of the algorithm is a spectral sparsification algorithm, which on an input of a graph A with n nodes and m edges returns a graph B with n-1+m/k edges, such that for all real vectors x, 1 (x^T B x)/(x^T A x) O(klog^2 n). The algorithm is randomized and runs in O(mlog^2 n) expected time. It is based on a simple and practical sampling procedure of independent interest. The sparsification algorithm and the solver simplify greatly the groundbreaking work of Spielman and Teng who were the first to design nearly linear time algorithms for SDD systems. Joint work with Gary Miller and Richard Peng



Other Videos By Microsoft Research


2016-08-17UCSD Distributed Cognition and Human-Computer Interaction Lab Research
2016-08-17Hardware Trojans in Wireless Cryptographic Integrated Circuits
2016-08-17Stable, Fair Societies As The Natural Product of Local Exchange Networks
2016-08-17Not All Frames Are Created Equal: Temporal Sparsity for Robust and Efficient ASR
2016-08-17California Fault Lines: Understanding the Causes and Impact of Network Failures
2016-08-17e-Heritage Projects in Italy, Cambodia, and Japan: Lesson learned
2016-08-17Self-Stabilizing Autonomic Recoverers
2016-08-17Embedding spanning trees in random graphs
2016-08-17Real-time estimation of distributed parameters systems: application to traffic monitoring
2016-08-17A Practical-Time Related-Key Attack on the KASUMI Cryptosystem Used in GSM and 3G Telephony
2016-08-17Spectral graph sparsification Part 2: [An O(mlog^2 n) algorithm for solving SDD systems]
2016-08-17MSR New England Social Media Research
2016-08-17Exploiting Sparsity in Unsupervised Classification
2016-08-17Computational Social Science in Medicine
2016-08-17Virtual Machine Reset Vulnerabilities; Subspace LWE; Cryptography Against Continuous Memory Attacks
2016-08-17Adaptive Submodularity: A New Approach to Active Learning and Stochastic Optimization
2016-08-17Spectral graph sparsification Part 1: -- (The Combinatorial Multigrid Solver)
2016-08-17Glauber Dynamics for the 2D Ising Model at Low Temperature
2016-08-17Sheriff: Detecting and Eliminating False Sharing
2016-08-17National Renewable Energy Lab, renewable energy and the compute space
2016-08-17Insights into Ad-sponsored Mobile Software


Tags:
microsoft research