# 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.

• Please don't simultaneously cross-post. – D.W. Feb 20 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).
• 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? – Mah Feb 20 at 15:28