# Problem conditions to use Laplacian solvers

I am trying to use Laplacian Solvers to solve a linear equation. I am just learning it (form here), so my question is very basic and it might not even make sense.

Suppose that we want to solve Ax=b, where matrix A is not a Laplacian matrix. Under what condition on A and b, we can solve Ax=b using Laplacian solvers?

P.S. Introducing a good reference will be helpful too.

– D.W.
Feb 20, 2021 at 6:13

It's a good question. You can use a Laplacian solver if $$A$$ is symmetric and diagonally semi-dominant (SDD). This is the subject of Theorem 9.2 in your reference book from Vishnoi. A good exposition of the proof (which was originally by Gremban) can be found in Appendix A of the paper by Kelner, Orecchia, Sidford and Zhu (arXiv:1301.6628).

A recent result by Kyng and Zhang (arXiv:1705.02944) suggests that current Laplacian solvers are probably restricted to this class.

• Unfortunately the matrix $A$ in my equation is not SDD, but it is sparse. Is there any other approach that I can use to solve it fast?