3
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Please don't simultaneously cross-post. $\endgroup$ – D.W. Feb 20 at 6:13
3
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Thanks a lot. Your answer and the references are really helpful. $\endgroup$ – Mah Feb 20 at 15:23
  • $\begingroup$ 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? $\endgroup$ – Mah Feb 20 at 15:28
  • 1
    $\begingroup$ For general sparse matrices you can do slightly better. See e.g. arXiv:2007.10254 and references therein. $\endgroup$ – smapers Feb 21 at 14:20
  • $\begingroup$ Great! This is exactly what I was looking for. $\endgroup$ – Mah Feb 21 at 17:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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