2
$\begingroup$

This semester, I have been studying the most popular iterative methods, i.e., Krylov subspace iteration methods. For a large sparse system linear $$ Ax=b, $$ where $A$ is nonsingular, I know that direct methods are not suitable for this. So a number of iterative methods have been proposed, such as classic stationary iteration methods, like Jacobi, Gauss-Seidel, SOR, etc. But when the system size becomes larger, the convergence rate becomes slower and the optimal parameter for SOR is hard to choose.

Then Krylov subspace methods are required, like CG, GMRES, MINRES, etc., which are faster than those classical iteration methods. Furthermore, I have done the numerical examples in MATLAB, and the results indeed prove the faster convergence rate of Krylov methods.

My question is though Krylov subspace methods indeed are faster than classical iteration methods, but why? I mean, where can be seen that Krylov methods can be faster than those classical methods? I just know that Krylov methods must converge within $N$ iterations, for a $N$ order matrix $A$ and it does not need to choose optimal parameter. But I still do not know why Krylov methods are faster than classical iteration methods? any suggestions?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ just a note that sparse direct and fast sparse direct methods are a thing: I have already outlined some notes to one of your previous questions. $\endgroup$
    – Anton Menshov ♦
    Dec 4, 2019 at 3:09
  • 1
    $\begingroup$ Most if not all classical iteration schemes can be cast into the framework of Krylov subspace methods. Also note that your assumption of convergence only applies to certain linear systems and/or iteration methods. Fast convergence usually involves preconditioning and the choice of suitable solvers. $\endgroup$
    – Christian Waluga
    Dec 4, 2019 at 6:45

1 Answer 1

Reset to default
5
$\begingroup$

I must admit I never actually checked all the details myself, but I think that's a sketch of the general idea.

  1. The $k$th iterate $x_k$ produced by Richardson iteration lies in the Krylov subspace $K_k(A,b)$.
  2. The $k$th iterate $x_k$ produced by a Krylov method typically minimizes some objective function inside that same Krylov space, hence it is "better" than Richardson.
  3. Jacobi is equivalent to Richardson with diag(A) as preconditioner, hence it is worse than a Krylov method with the same preconditioner.
  4. Gauss-Seidel is equivalent to Richardson with tril(A) as preconditioner.
Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks Prof. Poloni for your clear and simple explanation. Concisely speaking, the stationary iteration can be regarded as a Richard iteration, which obtains an approximate solution $x_k$ lying in the k-th Krylov subspace. However, the Krylov subspace methods produce an approximate solution $x_k$, which not only lies in the k-th Krylov subspace, but also minimize some function inside this Krylov subspace, e.g., the energy function for SPD matirx $A$, the 2-norm of residual $b-Ax_k$ for nonsymmetric matrix. So, it is seems "better" than stationary iteration method. Do I get your point? Thanks. $\endgroup$
    – Happy
    Dec 5, 2019 at 0:37
  • $\begingroup$ By the way, the k-th Richardson iteration $x_k = x_{k-1}+r_k$ obtains an approximate solution $x_k$ in the k-th Krylov subspace $K_k(A,b)$ for $x_0=0$. And the Jacobi iteration is a diagonally preconditioned Richardson iteration. Does this mean that the k-th Jacobi iteration produces an approximate solution $x_k$ which belongs to the preconditioned Krylov subsapce $K_k(M^{-1}A,b)$? Or the k-th Jacobi iteration still produces an approximate solution $x_k = x_{k-1} +M^{-1}r_{k-1}$, wher $r_k $ still in the same Krylov subspace $K_k(A,b)$? $\endgroup$
    – Happy
    Dec 5, 2019 at 3:33
  • $\begingroup$ @sunshine 1. Yes, I think that is correct. 2. $x_k$ from Jacobi belongs to the preconditioned Krylov subspace $K_k(D^{-1}A,b)$. Usually when studying these methods one defines an "iteration matrix" $P = D^{-1}(D-A)$ and works with that, but $P = I-D^{-1}A$ so that preconditioned Krylov subspace is the one that matters. $\endgroup$
    – Federico Poloni
    Dec 5, 2019 at 7:12

Your Answer

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

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