Exact 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 requires an exact solution with no error.

Related Problems

Related: Inexact Laplacian Solver

Parameters

$n$: dimension of matrix

Table of Algorithms

Name	Year	Time	Space	Approximation Factor	Model	Reference
Briggs; Henson; McCormick	2000	$O(n^{1.{2}5} \log \log n)$		Exact	Deterministic	Time
Gaussian Elimination	-150	$O(n^{3})$	$O(n^{2})$	Exact	Deterministic
Naive Implementation	1940	$O(n!)$	$O(n^{2})$	Exact	Deterministic

Time Complexity Graph