Exact Laplacian Solver (SDD Systems Solvers)

From Algorithm Wiki
Jump to navigation Jump to search


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


$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

SDD Systems Solvers - Exact Laplacian Solver - Time.png