A linear work, O(n^1/6) time, parallel algorithm for solving planar Laplacians

zbMATH Open1302.68308MaRDI QIDQ2934693FDOQ2934693

Authors: Ioannis Koutis, Gary L. Miller 

Publication date: 18 December 2014

Recommendations

• Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
• An efficient parallel solver for SDD linear systems
• Lx = b
• Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems
• Fast and Efficient Parallel Solution of Sparse Linear Systems

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Direct numerical methods for linear systems and matrix inversion (65F05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Parallel algorithms in computer science (68W10)

Cited In (10)

• A fast algorithm for manifold learning by posing it as a symmetric diagonally dominant linear system
• Title not available (Why is that?)
• Solving graph Laplacian systems through recursive partitioning and two-grid preconditioning
• Solving Local Linear Systems with Boundary Conditions Using Heat Kernel Pagerank
• On the discrete unit disk cover problem
• Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
• Accelerated multigrid for graph Laplacian operators
• A queueing network-based distributed Laplacian solver
• Parallelizable Global Conformal Parameterization of Simply-Connected Surfaces via Partial Welding
• The within-strip discrete unit disk cover problem

This page was built for publication: A linear work, \(O(n^{1/6})\) time, parallel algorithm for solving planar Laplacians

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2934693)