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
12 votes
Accepted

role of initial guess for iterative linear solver

Practical experience shows that trying to get good initial iterates has little value. For example, in the context of solving partial differential equations, if you take the solution from one mesh, ...
Wolfgang Bangerth's user avatar
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
9 votes
Accepted

Why MATLAB chooses the Householder in its built-in function gmres.m?

If you're using GMRES, typically you have a large stiff system. The extra work done for the householder algorithm is negligible compared to the expense of GMRES and the preconditionder. As such, we ...
EMP's user avatar
  • 2,089
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
6 votes

For which problems Krylov subspace methods are preferred over multigrid methods?

The answer depends somewhat on the discretization; for example, some boundary integral discretizations result in very well-conditioned matrices, for which a Krylov solver works just fine without ...
Jesse Chan's user avatar
  • 3,142
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
5 votes
Accepted

Why Krylov subspace iterative methods are faster than classical iteration?

I must admit I never actually checked all the details myself, but I think that's a sketch of the general idea. The $k$th iterate $x_k$ produced by Richardson iteration lies in the Krylov subspace $...
Federico Poloni'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
5 votes
Accepted

Does LAPACK offer routines for Krylov sub-space based solvers and nonlinear solvers?

As far as I know, there are no such methods in LAPACK. Since LAPACK is the linear algebra package, no nonlinear solvers are included. However, you can use the underlying BLAS for implementing ...
cos_theta's user avatar
  • 451
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
4 votes

For which problems Krylov subspace methods are preferred over multigrid methods?

This question is pretty well discussed in literature. However, there are lots of questions concerning multigrid on SciComp, so I decided to compose more or less detailed answer. I. When multigrid ...
56th's user avatar
  • 901
4 votes

Why does conjugate gradient work with this nonsymmetric preconditioner?

In short, orthogonalization of the Krylov vectors occurs with respect to the operator, but not with respect to the preconditioner. Alright, so say we want to solve $Ax=b$ with preconditioner $B$. ...
wyer33's user avatar
  • 767
4 votes

role of initial guess for iterative linear solver

It can be even harmful. In Liesen/Strakos Krylov subspace methods principles and analysis (Chapter 5.8.3) it is reported that a nonzero initial x0 makes a GMRes ...
Jan's user avatar
  • 3,418
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
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,693
4 votes

Ways to fix block Lanczos tridiagonalisation numerical instability for matrix with degenerate, closely spaced eigenvalues?

I'll expand into a full answer to get more space. The algorithms from LAPACK can provide both the eigenvectors and the eigenvalues. On symmetric/hermitian systems, like those for which Lanczos is ...
rchilton1980's user avatar
  • 4,862
3 votes
Accepted

How to understand the storage of the Hessenberg matrix of Krylov subspace matrix?

Your view is correct, Matlab does store the zeros. As pointed out by @rchilton1980, this particular non-optimization that you are pointing out here is not too harmful, since the bulk of the storage in ...
Federico Poloni's user avatar
3 votes
Accepted

How to understand the choice of Krylov subspace orthonormal basis?

I doubt I can explain this better than the author, but I'll give it a shot. Let's say that $r_0 = \sum \alpha_i x_i$, with $x_i$ an eigenvector with eigenvalue $\lambda_i$. We can then write the ...
Thijs Steel's user avatar
  • 1,693
3 votes

Questions about iterative projection methods in Saad book

In order to understand these results, you need to know how minimization and projection problems are connected. Namely, Let $\mathbb V$ be a subspace of $\mathbb C^n$ and take $y \in \mathbb C^n$; ...
56th's user avatar
  • 901
3 votes

role of initial guess for iterative linear solver

This answer is an addition to the one from Wolfgang Bangerth. It is certainly not worth to bother with the initial guess for the iterative linear solver if there is any work to be done: coding, ...
Anton Menshov's user avatar
  • 8,672
3 votes

PetSc vs Sundials for serial numerical computations?

As mentioned in Geoff Oxberry's more complete answer, it should be noted that PETSc includes TSSUNDIALS, an interface to SUNDIALS. If you configure PETSc with the ...
Patrick Sanan's user avatar
3 votes

PetSc vs Sundials for serial numerical computations?

In general, you can do more with PETSc. SUNDIALS is a collection of ODE solvers (in CVODE, Adams-Bashforth and BDF methods; in ARKODE, ARKIMEX methods) and DAE solvers (IDAS implements a BDF method) ...
Geoff Oxberry's user avatar
3 votes

CG without division by 0 in a solution

Either of $p_k$ or $r_k$ being zero implies exact convergence in exact arithmetic, so that is never a problem. Conjugate gradient was used as a direct solver for linear systems of equations much ...
Abdullah Ali Sivas's user avatar
3 votes

Does LAPACK offer routines for Krylov sub-space based solvers and nonlinear solvers?

LAPACK doesn't include any iterative solvers. The routines in LAPACK are for eigenvalues, matrix factorizations, and solutions of systems of equations involving dense matrices while iterative methods ...
Brian Borchers's user avatar
3 votes

Reason for why apparent acceleration of algebraic multigrid solve by addition of positive definite diagonal matrix

The computation in your update does most of the work towards a solution. You just need to note that $\frac{\varepsilon_1}{\varepsilon_2} \leq \frac{\max D_{ii}}{\min D_{ii}} = \kappa(D)$, and that $$ ...
Federico Poloni'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

Iterative single variable solutions in large linear systems

An approach by Papandreou and Yuille for diagonal $A$ relates variance estimation to the expectation of a quadratic form. The logic follows more generally: since $A$ is PD so is its inverse. Then $Z\...
VF1's user avatar
  • 211
2 votes

How to find a good preconditioner to the system $(A^T A + \lambda I) x = A^T b$?

Have you tried the preconditioner diag(A'*A)+lmb*speye(size(A))? For lmb large enough, I would imagine this preconditioner would ...
Abdullah Ali Sivas's user avatar
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

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