Inexact Laplacian Solver (SDD Systems Solvers)

Description

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.

Related Problems

Related: Exact Laplacian Solver

Parameters

$n$: dimension of matrix

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Spielman, Teng	2004	$O(m \log^c n)$	$O(n)$	\epsilon	Deterministic	Time
Vaidya	1990	$O(mn^{({3}/{4})$})	$O(n)$	\epsilon	Deterministic
Gremban; Miller; Zagha	1995	$O(n^{2})$	$O(n^{2})$	?	Deterministic	Time & Space
Bern; Gilbert; Hendrickson	2006	$O(n \log \log n)$		Exact	Deterministic	Time
Boman; Hendrickson	2003	$\tilde{O}(mn^{({1}/{2})})$		\epsilon	Deterministic	Time
Boman; Chen; Hendrickson; Toledo	2004	$O(n \log({1}/ϵ)$ )	$O(n)$	\epsilon	Deterministic	Time
Koutis; Miller and Peng	2010	$\tilde{O}(m \log n)$	$O(n)$	\epsilon	Deterministic	Time
Koutis; Miller and Peng	2011	$\tilde{O}(m \log n)$	$O(n)$	\epsilon	Deterministic	Time
Blelloch; Koutis; Miller; Tangwongsan	2010	$O(n \log n)$	m + $O(n/\log n)$	?	Deterministic	Time & Space
Briggs; Henson; McCormick	2000	$O(n^{1.{2}5} \log \log n)$		Exact	Deterministic	Time
Kelner; Orecchia; Sidford; Zhu	2013	$O(m \log^{2} (n)$ \log \log n)	$O(n)$	\epsilon	Deterministic	Time
Lee; Peng; Spielman	2015	$O(n)$	$O(n)$	The sparse Cholesky decomposition is a 2-approximation	Deterministic	Time
Daitch; Spielman	2007	$O(n^{5/4} (\log^{2} (n)$ \log\log n)^{3/4} \log({1}/ϵ))	$O(n)$	\epsilon	Deterministic	Time

Time Complexity Graph