1
$\begingroup$

when we solve a large sparse linear system Ax=b, using preconditioned Krylov subspace methods,e.g., gmres, should we need to reduce the condition number of the coefficient matrix? In my opinion, we just need to consider how to cluster the eigenvalues distribution of the preconditioned matrix M^{-1}A, as long as the spectra cluster, we can obtain fast convergence of the iteration, regardless of the magnitude of the condition number of the preconditioned matrix $M^{-1} A$. So, I think we do not need to consider the condition number. But a teacher said that we must reduce the condition number of the preconditioned matrix $M^{-1}A$, in his words, one must consider how the condition number become? But I still hold that we need not consider the condition number. For example, if a symmetric positive matrix $A$ just has two distinct eigenvalues, PCG will converges in 2 steps whatever size does this matrix $A$ has. let alone the condition number.

Do I right or the teacher right? Thanks

Improve this question
$\endgroup$
2
  • $\begingroup$ Note that if the eigenvalues cluster around zero, as happens for example when discretizing a smoothing operator, the condition number will be right in warning you that convergence will be slow. $\endgroup$
    – Amit Hochman
    Commented Oct 17, 2019 at 15:16
  • $\begingroup$ Try running GMRES on the upper triangular toeplitz matrix with 1's on the diagonal, 2's on the first superdiagonal, 3's on the second superdiagonal, and so on. The eigenvalues are all $1$, but the conditioning of the eigenvector matrix is horrendous so GMRES converges slowly. $\endgroup$
    – Nick Alger
    Commented Oct 17, 2019 at 15:18

1 Answer 1

Reset to default
2
$\begingroup$

The condition number of a matrix $A$ is used primarily for two things:

  1. To understand how much accuracy we can expect when solving $Ax=b$
  2. as a rough idea of how hard it might be to solve $Ax=b$ iteratively

You already pointed out that for (2) the condition number doesn't really tell the whole story. If the matrix is symmetric and positive definite then most iterative solvers will have some kind of convergence rate provable in advance based only on the condition number, but it's usually not a very useful estimate.

You also point out that eigenvalue clustering appears to fully determine convergence behavior of many iterative solvers. This is largely true, but it also comes with some caveats: most of the time the matrix must be normal for eigenvalue clustering arguments to work. Thus even this more general criteria can be misleading.

Therefore in practice it's best to think holistically about iterative solvers: look at conditioning, spectrum, normality, and try to determine a preconditioner which is cheap to evaluate but can control those three properties in a way that is beneficial.

For a more mathematical look at this, consider checking out the answers to this related question

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.