Inexact Laplacian Solver

This problem refers to solving equations of the form $Lx = b$ where $L$ is a Laplacian of a graph. In other words, this is solving equations of the form $Ax = b$ for a SDD matrix $A$ . This variation of the problem permits some error.

Parameters

$n$ : dimension of matrix

Filters

Computational Model

Randomization

Approximation

Algorithms Table

Displaying 10 of 10 algorithms


Lee; Peng; Spielman	2015	$O(n)$	$O(n)$
Kelner; Orecchia; Sidford; Zhu	2013	$O(m \log^2(n) \log \log n)$	$O(n)$
Koutis; Miller and Peng	2011	$\tilde{O}(m \log n)$	$O(n)$
Koutis; Miller and Peng	2010	$\tilde{O}(m \log n)$	$O(n)$
Blelloch; Koutis; Miller; Tangwongsan	2010	$O(n \log n)$	$m + O(n/\log n)$
Daitch; Spielman	2007	$O(n^{5/4} (\log^2(n) \log\log n)^{3/4} \log(1/\epsilon))$	$O(n)$
Spielman, Teng	2004	$O(m \log^c n)$	$O(n)$
Boman; Chen; Hendrickson; Toledo	2004	$O(n\log(1/\epsilon))$	$O(n)$
Gremban; Miller; Zagha	1995	$O(n^2)$	$O(n^2)$
Vaidya	1990	$O(mn^{3/4})$	$O(n)$

Reductions Table

Insuffient Data to display table

Other relevant algorithms

Displaying 1 of 1 other relevant algorithms