Hot answers tagged

16 votes
Accepted

What are the major differences between GMRES and FOM?

There is one major difference between GMRES over FOM. It is also the reason why I would recommend GMRES over FOM. In exact arithmetic, the residuals obtained by GMRES form a decreasing sequence. You ...
Carl Christian's user avatar
13 votes
Accepted

When do not use preconditioners for sparse linear system of equations?

In my experience, you always need (or better use) some form of preconditioning. The type and complexity of the precondition would vary depending on the task though. From Y. Saad, Iterative Methods for ...
Anton Menshov's user avatar
  • 8,652
11 votes
Accepted

A numerical GMRES example

GMRES is indeed one of the hardest to understand Krylov methods. As you correctly state, the algorithm computes in each step $m$ a new approximation $x^m$ to the solution of $Ax=b$ as a minimizer of $\...
Christian Clason's user avatar
10 votes
Accepted

How does gmres method iteration behave for this non-diagonalizable matrix?

Unfortunately, convergence of GMRES does not have a clear dependence on the distribution of eigenvalues. It was proved by Greenbaum, Ptak and Strakos in 1996 that you can construct examples with an ...
Federico Poloni's user avatar
7 votes

Operation count for GMRES

Performing $k$ steps of GMRES uses $O(n k^2)$ time and $O(n k)$ memory. In other words, the algorithm gets more and more expensive with each additional iteration. In theory, the algorithm terminates ...
Richard Zhang's user avatar
7 votes
Accepted

Why do not we choose the error solution norm as an iterative method's criterion?

We can't use the criterion you show last in practice because it requires us to know what $\kappa(A)$ is. But computing the condition number is, in general, more expensive than solving a linear system. ...
Wolfgang Bangerth's user avatar
6 votes

Why minimizing with respect to A-norm?

Wolfgang Bangerth's answer already says almost everything, but another subtle detail is that GMRES/MINRES minimize the norm of the residual, i.e., $\|Ax_k-b\|$, while CG minimizes the (A-)norm of the ...
Federico Poloni's user avatar
6 votes
Accepted

GMRES vs Newton-GMRES for Solving nonlinear PDE's

The reason is that GMRES can only be used for solving linear equations, i.e. equations of the form $Ax=b$, where $A$ is some matrix and $x,b$ are vectors. What GMRES does, essentially, is it ...
bgav's user avatar
  • 106
6 votes

A numerical GMRES example

The intuition behind all Krylov's subspace methods is the following. Given a square matrix $A$ and a compatible vector $b$, there exists a unique monic polynomial $p$ such that $p(A)b = 0$. ...
Carl Christian's user avatar
5 votes

MATLAB: code for restarted gmres

Technically, the template Matlab code provided at Netlib already calculates the obtained residual at every iteration. It's just not recorded in the way that this is an output of the subroutine. After ...
Anton Menshov's user avatar
  • 8,652
5 votes

How does gmres method iteration behave for this non-diagonalizable matrix?

Estimates for GMRES convergence based on eigenvalue distribution often implicitly assume that the matrix is normal. Sometimes the convergence rate is still provable in an asymptotic sense in the non-...
Reid.Atcheson's user avatar
5 votes
Accepted

Why minimizing with respect to A-norm?

In some sense it doesn't matter: In finite dimensions, all norms are equivalent, so if an algorithm conveniently has the property that proving convergence in one norm is easy, then that's what people ...
Wolfgang Bangerth's user avatar
5 votes
Accepted

How to implement flexible gmres in matlab?

First of all, MATLAB's gmres assumes that the preconditioner you use is linear. This is important! Actually it is the main difference between FGMRES and GMRES. ...
Abdullah Ali Sivas's user avatar
4 votes
Accepted

What's wrong with the **PCG and MINRES** in matlab?

While very similar, each method is slightly different and you should definitely take this into account. The GMRES method is the simplest, it will construct an orthogonal basis for $\mathcal{K}_k(A,b)$...
Thijs Steel's user avatar
  • 1,558
4 votes

How GMRES method finds smallest singular value and the corresponding singular vectors of a matrix?

How GMRES method finds smallest singular value and the corresponding singular vectors of a matrix? It doesn't. GMRES solves linear systems. Your citation probably refers to other Krylov methods: ...
Federico Poloni's user avatar
3 votes
Accepted

Preconditioner for the GMRES method in the Uzawa algorithm

Please check this paper by Benzi et al. They address this issue and give corresponding references on p. 45. Shortcut: for the Stokes problem $A = \text{diag}(A_{11},A_{11},\dots,A_{11})$ is just a ...
56th's user avatar
  • 901
2 votes

Why do we need orthonormal basis of Krylov subspaces for GMRES?

Since nobody else has answered this question (which is a good question, by the way!) so far, I'm consolidating my comments here. Briefly, GMRES boils down to three key ideas: Construct a sequence of ...
Christian Clason's user avatar
2 votes

GMRES : incomplete Krylov-subspace

I'm not sure I understand the question, but in GMRES you built a orthonormal base for the space $K_m \; \text{ for } m= 1 \dots N$. In this space the generic vector can be write as: $$ x = x_0 + V_m y$...
Mauro Vanzetto's user avatar
2 votes
Accepted

Preconditioner for dense matrix "with diagonal predominance"

In case it may be of help to others, here's the result of the testing on a 30x30 influence matrix.It was made using non-restarted GMRES. GMRES without preconditioner (red curve) converges in 13 ...
techwinder's user avatar
2 votes
Accepted

How to pass matrices to parallel workers quickly in matlab?

It seems like you have $N$ systems of linear equations that you need to solve. Let's say that you have $P$ cores available to you and unlimited memory. Now, you have two options: You can try solving $...
Anton Menshov's user avatar
  • 8,652
2 votes

How does gmres method iteration behave for this non-diagonalizable matrix?

Well, I can only propose a potential cause for why GMRES method fails for the problem you showed. I don't have enough reputation so I can't comment. Since GMRES is using Anorldi Process to generate ...
Sen's user avatar
  • 21
2 votes
Accepted

Does the k-th approximate solution of a stationary iteration belong to the k-th Krylov subspace?

Taking $x_0 = 0$, we have that $x_1 \in <M^{-1}b>$. For the next iteration, we get $x_2 \in <M^{-1}b, M^{-1}AM^{-1}b>$. For the next iteration, we get $x_3 \in <M^{-1}b, (M^{-1}A)^2M^{...
Thijs Steel's user avatar
  • 1,558
2 votes

Doubt regarding GMRES(m) and preconditioned GMRES

It's just a difference in how the authors decided to write the algorithm. Left-preconditioned GMRES is the same as regular GMRES where $A$ is replaced with $M^{-1}A$ and $b$ is replaced with $M^{-1}b$....
Neil Lindquist's user avatar
1 vote

relres in gmres MATLAB

The advantage of that definition is that computing relres comes "for free" from the GMRES iteration. You could switch to the other definition without the preconditioner, but then you'd have ...
Federico Poloni's user avatar
1 vote

How GMRES method finds smallest singular value and the corresponding singular vectors of a matrix?

I kinda see what you are asking. There is a relationship between singular values of a matrix $A$ and the matrix $A^HA$: $\sigma_i^2(A)=\lambda_i(A^HA)$. So in theory, you can use inverse power method ...
Abdullah Ali Sivas's user avatar
1 vote

Library to solve dense linear system with GMRES

PETSC might be a good option. Not super user friendly, but its good with lots of options.
EMP's user avatar
  • 2,079
1 vote

How does gmres method iteration behave for this non-diagonalizable matrix?

First some comments on why such matrices are hard for solvers. Notice that if $U$ is upper diagonal like ...
denis's user avatar
  • 932
1 vote

Number of GMRES iterations increase when stepping forward in time, using the Newton method

It looks to me like the most helpful thing you can do is increase the number of krylov vectors you are using. This is somewhat different from the typical behavior I've seen where the first step takes ...
EMP's user avatar
  • 2,079
1 vote

How to set an initial guess for the iterative solver in Comsol?

I am not too familiar with the details of the iterative solve in Comsol; however, quick googling did reveal any easy way to set up a custom initial guess for an iterative linear solver. (I ready to be ...
Anton Menshov's user avatar
  • 8,652
1 vote

GMRES : incomplete Krylov-subspace

If $A$ is invertible and the Krylov subspace $v,Av,A^2v,\ldots$ stops to expand after $m$ steps, then GMRES (and other reasonable Krylov methods) converge to the exact solution in at most $m$ steps (...
Convexity's user avatar
  • 161

Only top scored, non community-wiki answers of a minimum length are eligible