Which iterative linear solvers converge for positive semidefinite matrices?

Question

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)

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 03 '12 at 07:36
CG and its derivatives (BiCG, CGNE etc.) will converge for positive definite matrices. During the computation of CG solutions, there is a $x^TAx$ term in the denominator which will cause Divide-by-zero in case that term is 0. Gauss-Seidel and Jacobi, as far as I know, need diagonally dominant matrices or Symmetric PD matrices. — Inquest, Mar 03 '12 at 08:09
@Nunoxic at least for CG, you are mistaken - CG is guaranteed to converge for Positive semidefinite matrices, that is, it will reach a solution $x$ s.t |Ax-b|=0 in case $b \in span(A) $ — olamundo, Mar 03 '12 at 13:56
Are you sure? If you check out Wikipedia, the head does state that the matrix needs to be Positive Definite and also, if you see the link during the calculation of $\alpha$, the denominator would run to 0 (at some point of time) if the matrix wasn't strictly positive definite. — Inquest, Mar 03 '12 at 14:04
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 03 '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 04 '12 at 00:53
@faleichik: reduced density matrices in quantum mechanics are positive semi-definite in very many cases. — Deathbreath, Mar 04 '12 at 00:56
Perhaps you could take a look at: http://www.cs.yale.edu/homes/spielman/PAPERS/icm10post.pdf — usero, Apr 09 '12 at 08:46

score 8 · Accepted Answer · answered Mar 08 '12 at 11:54

8

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

answered Mar 08 '12 at 11:54

Arnold Neumaier

11,318
20
47

thanks. Any idea about the "archaic" solvers, e.g SOR Gauss-Seidel etc. – olamundo Mar 08 '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 09:18

score 1 · Answer 2 · edited Sep 11 '18 at 14:04

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.

Which iterative linear solvers converge for positive semidefinite matrices?

2 Answers2

Linked