2
$\begingroup$

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.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
2
$\begingroup$

Apparently, Daniel Spielman (one of the authors of said result) maintains a page 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 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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.