<p>Apparently, Daniel Spielman (one of the authors of said result) maintains <a href="https://sites.google.com/a/yale.edu/laplacian/" rel="nofollow noreferrer">a page</a> regarding the topic. It has a “code” section:</p>
<blockquote>
<p>If you need to solve diagonally-dominant linear systems, I also suggest trying the Algebraic Multigrid algorithm. You can find an implementation in the LAMG package, written by Oren Livne.</p>
</blockquote>
<p>The <a href="https://code.google.com/archive/p/lamg/" rel="nofollow noreferrer">library</a> seems to be written in Matlab (yuck),  but seems specifically tailored for the purpose. I’ll give it a try and report how well it does in a comment here.</p>

CC BY-SA 4.0
2022-11-07T10:50:37.703Z
2022-11-07T10:50:37.703Z
user3508551
<p>Aren't Finite Element Methods or Vector-Fitting or Fast-Multi-pole-Method   a kind of solution for laplacian equations?  They are implemented well in many programming languages.</p>

CC BY-SA 4.0
2022-11-07T14:04:50.290Z
2022-11-07T14:04:50.290Z
morteza
<p>In a much celebrated result, we know that there is a <span class="math-container">$ O(m\log \frac{1}{\epsilon}) $</span> time algorithm for solving laplacian systems of the form <span class="math-container">$Lx=b$</span> where <span class="math-container">$L$</span> is a laplacian of a graph <span class="math-container">$G$</span> with <span class="math-container">$m$</span> edges to within <span class="math-container">$\epsilon$</span> accuracy (skipping some of the technical details).</p>
<p>As far as I know, the algorithm is quite involved, and not really practical to implement. I am curious if there are known fast practical algorithms that can solve such systems to close the gap between theory and practice? Obviously, you can feed the
Laplacian to a linear system solver, but I wonder if some solvers can exploit the Laplacian nature to speed up the computation.</p>

<linear-algebra>
Are there publicly available fast Laplacian solvers?
user3508551
# Are there publicly available fast Laplacian solvers?

(Asked by: username_0 on 2022-11-05)

In a much celebrated result, we know that there is a $ O(m\log \frac{1}{\epsilon}) $ time algorithm for solving laplacian systems of the form $Lx=b$ where $L$ is a laplacian of a graph $G$ with $m$ edges to within $\epsilon$ accuracy (skipping some of the technical details).

As far as I know, the algorithm is quite involved, and not really practical to implement. I am curious if there are known fast practical algorithms that can solve such systems to close the gap between theory and practice? Obviously, you can feed the
Laplacian to a linear system solver, but I wonder if some solvers can exploit the Laplacian nature to speed up the computation.

**Tags:** linear-algebra

---

## 2 answers

### Answer by username_0 on 2022-11-07. Score: 2

Apparently, Daniel Spielman (one of the authors of said result) maintains [a page](https://sites.google.com/a/yale.edu/laplacian/) regarding the topic. It has a “code” section:

> If you need to solve diagonally-dominant linear systems, I also suggest trying the Algebraic Multigrid algorithm. You can find an implementation in the LAMG package, written by Oren Livne.

The [library](https://code.google.com/archive/p/lamg/) seems to be written in Matlab (yuck), but seems specifically tailored for the purpose. I’ll give it a try and report how well it does in a comment here.


---

### Answer by username_1 on 2022-11-07. Score: 0

Aren't Finite Element Methods or Vector-Fitting or Fast-Multi-pole-Method a kind of solution for laplacian equations? They are implemented well in many programming languages.


---

