1

Given is a system of linear equations $Ax=b$ and $A$ is of size n-by-n. If we use the generalized minimal residual method (GMRES) we iteratively calculate approximate solutions for Krylov subspaces of increasing dimension. Usually we abort prematurely, but eventually the Krylov subspace would be of the dimension $n$.

Doesn't that imply that GMRES is a direct solver instead of an iterative one since it should take at most $n$ steps to find a sufficient solution? Does it depend on the circumstances (e.g. the accuracy of the calculation)?

koalo
  • 103
  • 2
    Iterative in the same way that conjugate gradients is iterative. – copper.hat Oct 14 '18 at 20:36
  • 1
    "it should take at most n steps to find a sufficient solution" is not an absolute truth. GMRES is undisputably an iterative method. –  Oct 14 '18 at 20:45
  • the convergence depends on what you set the precision for and the eigenvalues of the matrix $A$ , so very ill-conditioned matrices converge slowly –  Oct 14 '18 at 21:15
  • @Yves Daoust: So what to do next after n steps? There is no dimension left to construct a new Krylov subspace... – koalo Oct 15 '18 at 06:40
  • https://en.wikipedia.org/wiki/Generalized_minimal_residual_method#The_method –  Oct 15 '18 at 07:25
  • @Yves Daoust OK, yes according to that we just include A^{n+1}b, A^{n+2}b.... in the Krylov subspace, but since A is a n-by-n matrix that would not increase the dimension of the subspace. – koalo Oct 15 '18 at 07:41
  • repeat if the residual is not yet small enough.
    • –  Oct 15 '18 at 07:45
  • http://pi.math.cornell.edu/~web6140/TopTenAlgorithms/KrylovSubspace.html –  Oct 15 '18 at 18:09