I want to know which of the classic linear solvers (e.g Gauss-Seidel, Jacobi, SOR) are guaranteed to converge for the problem $Ax=b$ where $A$ is positive semi definite and of course $b \in im(A)$
(Notice $A$ is semi definite and not definite)
$\begingroup$
$\endgroup$
12
-
1$\begingroup$ Do you mean positive semi-definite matrices? $\endgroup$– meawopplMar 2, 2012 at 8:57
-
1$\begingroup$ What's the use of solving linear system with such matrix? If I'm not mistaken, if your positive semidefinite matrix is non-singular then it is simply positive definite. $\endgroup$– faleichikMar 3, 2012 at 7:36
-
1$\begingroup$ Yes, I am sure. I have to refresh my memory as for the actual proof, but per what you were saying - if the denominator in the calculation of $\alpha$ is zero, it means that $A P_k$ is zero, which means that all the "search directions" in which A is not singular have been exhausted, and the residual you are left with in not in the span of A (and thus this is the "optimal" solution). In the case that in fact $b \in span(A)$, this won't happen as the residual will reach zero just before the first time $AP_k=0$ $\endgroup$– olamundoMar 3, 2012 at 15:47
-
1$\begingroup$ Set $x_0=b$. Then $A^nb\in Im(A)$. CG will converge due to $x_n^\ast Ax_n> 0$ for all $0\ne x_n\in Im(A)$. In other words, you never leave $Im(A)$ for which $A$ is positive-definite. $\endgroup$– DeathbreathMar 4, 2012 at 0:53
-
2$\begingroup$ @faleichik: reduced density matrices in quantum mechanics are positive semi-definite in very many cases. $\endgroup$– DeathbreathMar 4, 2012 at 0:56
|
Show 7 more comments
2 Answers
$\begingroup$
$\endgroup$
3
The conjugate gradient algorithm works for semidefinite problems and produces the minimal norm solution.
-
$\begingroup$ thanks. Any idea about the "archaic" solvers, e.g SOR Gauss-Seidel etc. $\endgroup$– olamundoMar 8, 2012 at 18:33
-
$\begingroup$ They are hardly ever used anymore, and I don't know how these behave. $\endgroup$ Mar 12, 2012 at 18:16
-
$\begingroup$ To clarify: CG most certainly does not work in vanilla form for semi-definite matrices; it may work in theory if B is in the image of A; but this is unlikely to end well in numerical-practice. The very similar krylov-based MINRES is a much better choice here. Also, these "archaic" solvers are widely used in multigrid-type solvers, to name one example. $\endgroup$ Sep 11, 2018 at 9:18
$\begingroup$
$\endgroup$
Here is a proof that Gauss-Seidel fits your requirements, given that $b$ is in the image of $A$.
The same is very much not true of Jacobi; which is a shame since who wants to bother with Gauss-Seidel on modern computer hardware? If your problem can be split into diagonally-dominant blocks, you are in luck; you can apply Jacobi updates to those blocks in an incremental Gauss-Seidel fashion, and get the best of both for these type of semi-definite problems.
