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

MaRDI QIDQ2934693zbMATHFDO

Authors Ioannis Koutis, Gary L. Miller

Publication date 18 December 2014

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)

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

Cited in

(12)

• The power of vertex sparsifiers in dynamic graph algorithms
• A queueing network-based distributed Laplacian solver
• Solving 1-Laplacians in nearly linear time: collapsing and expanding a topological ball
• Solving graph Laplacian systems through recursive partitioning and two-grid preconditioning
• Accelerated multigrid for graph Laplacian operators
• Parallelizable global conformal parameterization of simply-connected surfaces via partial welding
• Solving local linear systems with boundary conditions using heat kernel pagerank
• On the discrete unit disk cover problem
• The within-strip discrete unit disk cover problem
• Nearly-linear work parallel SDD solvers, low-diameter decomposition, and low-stretch subgraphs
• A fast algorithm for manifold learning by posing it as a symmetric diagonally dominant linear system
• Hodge decomposition and general Laplacian solvers for embedded simplicial complexes

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)