3
$\begingroup$

I have two matrices $A, B$ coming from a finite element discretization of a system of partial differential equations. $A$ represents the system matrix and is symmetric and indefinite. $B$ is symmetric positive definite and is used as a preconditioner. Direct solver is used for computation of action of $B^{-1}$. The preconditioner is quite good, $\sigma(B^{-1}A) \subset (-10, -0.1) \cup (0.1, 10)$.

When I solve this system using GMRES preconditioned by $B$ I get the approximate solution after a reasonable number of iterations. However the same preconditioner fails when used in MINRES. The number of iterations for the preconditioned system is even higher than for unpreconditioned system. (I tried this computation using PETSc, Matlab and scipy with the same qualitative result.)

Could you please navigate me to some theoretical result or a keyword that would explain such behaviour?

Edit: I found a mistake in my code, the question is no longer valid, $B$ was (slightely) not symmetric which makes MINRES useless. My deepest apologies.

$\endgroup$
  • $\begingroup$ @FedericoPoloni Thanks for the comment. I think it should be ok now. $\endgroup$ – Korf Jul 22 '17 at 19:47
2
$\begingroup$

Are you applying MINRES to the operator $B^{-1}A$? Unless $B$ and $A$ commute, which is unlikely, the product $B^{-1}A$ is not symmetric. I'm guessing that this is what happened in your case because GMRES, which works even for nonsymmetric matrices, did converge, while MINRES did not.

You mentioned using a direct factorization of $B$. Provided you used the Cholesky decomposition $B = LL^*$, then the matrix $L^{-1}AL^{-*}$ is symmetric. If you apply MINRES to this system you might have better luck.

It's a little weird that the preconditioned system requires more iterations than the original system. But, all the nonsymmetric iterative methods have weird failure modes and can be made to converge slowly on certain input matrices. See this paper for examples. In any case, you mentioned using PETSc, so you can always try other preconditioners and see what works best.

$\endgroup$
2
$\begingroup$

Using a preconditioner $B$ for solving the system $Ax=b$ does not correspond to solving the system $B^{-1}Ax = B^{-1}b$, since, as Daniel pointed out, $B^{-1}A$ is generally not symmetric. Rather, it corresponds to solving $$ B^{-1/2} A B^{-1/2} \tilde{x} = B^{-1/2}b. $$ You could also formally consider the system $$ B^{-1}Ax = B^{-1}b $$ and use the inner product $\left\langle\cdot,\cdot\right\rangle_B$, or the system $$ AB^{-1}\tilde{x} = B^{-1}b $$ and use the inner product $\left\langle\cdot,\cdot\right\rangle_{B^{-1}}$. All three viewpoints will lead to the exact same algorithm, the preconditioned MINRES. (The same with CG, btw.)

Note that the spectrum is equal for all three systems, $$ \sigma(B^{-1/2} A B^{-1/2}) = \sigma(B^{-1}A) = \sigma(AB^{-1}), $$ so looking at $\sigma(B^{-1}A)$ is okay.

As to why MINRES and GMRES differ in convergence behavior is hard to say. Perhaps you made the mistake of applying MINRES to $B^{-1}A$. If not, another explanation could be loss of orthogonality in MINRES. Note that for symmetric matrices in exact arithmetic MINRES and GMRES to exactly the same thing. The difference is that GMRES keeps a basis of Krylov space to orthogonalize against, while MINRES relies on certain properties to only orthogonalize against the last few vectors. This could be error-prone. Since the two algorithms do exactly the same thing, some people say that

GMRES is the most robust MINRES implementation.

If you're not short on memory, GMRES is certainly safe to use.

$\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.