# Which iterative linear solvers converge for positive semidefinite matrices?

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)

• Do you mean positive semi-definite matrices? – meawoppl Mar 2 '12 at 8:57
• 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. – faleichik Mar 3 '12 at 7:36
• 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$ – olamundo Mar 3 '12 at 15:47
• 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. – Deathbreath Mar 4 '12 at 0:53
• @faleichik: reduced density matrices in quantum mechanics are positive semi-definite in very many cases. – Deathbreath Mar 4 '12 at 0:56

## 2 Answers

The conjugate gradient algorithm works for semidefinite problems and produces the minimal norm solution.

• thanks. Any idea about the "archaic" solvers, e.g SOR Gauss-Seidel etc. – olamundo Mar 8 '12 at 18:33
• They are hardly ever used anymore, and I don't know how these behave. – Arnold Neumaier Mar 12 '12 at 18:16
• 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. – Eelco Hoogendoorn Sep 11 '18 at 9:18

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.