10
$\begingroup$

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)

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

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

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

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.

$\endgroup$

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.