Sparsified Cholesky and multigrid solvers for connection laplacians

DOI10.1145/2897518.2897640zbMath1378.65079arXiv1512.01892OpenAlexW2295766446MaRDI QIDQ5361884

Richard Peng, Yin Tat Lee, Sushant Sachdeva, Rasmus Kyng, Daniel A. Spielman

Publication date: 29 September 2017

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

Full work available at URL: https://arxiv.org/abs/1512.01892

zbMATH Keywords

parallel algorithmslinear system solversSDD linear systemsconnection Laplacians

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Factorization of matrices (15A23) Parallel numerical computation (65Y05) Complexity and performance of numerical algorithms (65Y20) Direct numerical methods for linear systems and matrix inversion (65F05) Linear equations (linear algebraic aspects) (15A06)

Related Items (19)

Expansion in matrix-weighted graphs ⋮ Randomized numerical linear algebra: Foundations and algorithms ⋮ Constructing Linear-Sized Spectral Sparsification in Almost-Linear Time ⋮ 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 ⋮ Hardness of graph-structured algebraic and symbolic problems ⋮ 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 ⋮ Determinant-Preserving Sparsification of SDDM Matrices ⋮ Unnamed Item ⋮ The geometry of synchronization problems and learning group actions ⋮ Using Petal-Decompositions to Build a Low Stretch Spanning Tree ⋮ Parallelizable Global Conformal Parameterization of Simply-Connected Surfaces via Partial Welding ⋮ Density Independent Algorithms for Sparsifying k-Step Random Walks ⋮ Approximation of the Diagonal of a Laplacian’s Pseudoinverse for Complex Network Analysis ⋮ A spectral approach to the shortest path problem ⋮ Unnamed Item

This page was built for publication: Sparsified Cholesky and multigrid solvers for connection laplacians