<p>It's a good question. You can use a Laplacian solver if <span class="math-container">$A$</span> 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 (<a href="https://arxiv.org/abs/1301.6628" rel="nofollow noreferrer">arXiv:1301.6628</a>).</p>
<p>A recent result by Kyng and Zhang (<a href="https://arxiv.org/abs/1705.02944" rel="nofollow noreferrer">arXiv:1705.02944</a>) suggests that current Laplacian solvers are probably restricted to this class.</p>

CC BY-SA 4.0
2021-02-20T15:23:32.410Z
Thanks a lot. Your answer and the references are really helpful.
Mah
CC BY-SA 4.0
2021-02-20T15:28:15.560Z
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
CC BY-SA 4.0
2021-02-21T14:20:47.197Z
For general sparse matrices you can do slightly better. See e.g. [arXiv:2007.10254](https://arxiv.org/abs/2007.10254) and references therein.
smapers
CC BY-SA 4.0
2021-02-21T17:25:45.937Z
Great! This is exactly what I was looking for.
Mah
CC BY-SA 4.0
2021-02-19T18:11:21.283Z
2021-02-19T18:11:21.283Z
smapers
<p>I am trying to use Laplacian Solvers to solve a linear equation. I am just learning it (form <a href="https://www.cs.yale.edu/homes/vishnoi/Lxb-Web.pdf" rel="nofollow noreferrer">here</a>), so my question is very basic and it might not even make sense.</p>
<p>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>
<p>P.S. Introducing a good reference will be helpful too.</p>

CC BY-SA 4.0
2021-02-20T06:13:28.100Z
Please don't simultaneously cross-post.
D.W.
<graph-theory><graph-algorithms><linear-algebra><matrices><sparse-matrix>
Problem conditions to use Laplacian solvers
Mah
# Problem conditions to use Laplacian solvers

(Asked by: username_0 on 2021-02-19)

I am trying to use Laplacian Solvers to solve a linear equation. I am just learning it (form [here](https://www.cs.yale.edu/homes/vishnoi/Lxb-Web.pdf)), 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.

**Tags:** graph-theory, graph-algorithms, linear-algebra, matrices, sparse-matrix

> **Comments:**
> **username_1**: Please don't simultaneously cross-post.  

---

## 1 answers

### Answer by username_2 on 2021-02-19. Score: 3 | Accepted answer

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](https://arxiv.org/abs/1301.6628)).

A recent result by Kyng and Zhang ([arXiv:1705.02944](https://arxiv.org/abs/1705.02944)) suggests that current Laplacian solvers are probably restricted to this class.

> **Comments:**
> **username_0**: Thanks a lot. Your answer and the references are really helpful.  
> **username_0**: 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?  
> **username_2**: For general sparse matrices you can do slightly better. See e.g. [arXiv:2007.10254](https://arxiv.org/abs/2007.10254) and references therein.  
> **username_0**: Great! This is exactly what I was looking for.  

---

