15 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 ...
user avatar
12 votes
Accepted

How is Krylov-accelerated Multigrid (using MG as a preconditioner) motivated?

In some cases, (F)MG provides an algorithm with optimal properties. For instance, properly tuned FMG can solve some elliptic problems in a small number of "work units", where a work unit is defined to ...
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, ...
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 $\...
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 ...
user avatar
  • 1,902
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$. ...
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 ...
user avatar
  • 3,023
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 ...
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 $...
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. ...
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 ...
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)$...
user avatar
  • 1,189
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 ...
user avatar
  • 861
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 ...
user avatar
  • 3,408
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$. ...
user avatar
  • 697
4 votes
Accepted

Appropriate iterative linear solver for an eigenvalue problem

If your matrices are large, why not use a library like ARPACK? The shift-and-invert mode of ARPACK will help you calculate the eigenvalues close to $\sigma$. There are interfaces to ARPACK for most ...
user avatar
  • 2,116
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: ...
user avatar
4 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 ...
user avatar
  • 401
3 votes
Accepted

Algorithm to calculate the exponential of an Hessenberg matrix

Since expokit seems to use a Krylov subspace method, usually (at least, the hope is that) the upper Hessenberg matrices are of small dimension, say $m \sim 100$. For matrices of these sizes, there ...
user avatar
3 votes

Choosing preconditioner for unsymmetric pressure-velocity coupled system

Both ILU and diagonal scaling are not efficient preconditioners for "real" problems, i.e., if you let the size of your discrete problem become large. In other words, if you insist on timing GPUs vs ...
user avatar
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, ...
user avatar
  • 8,451
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 ...
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) ...
user avatar
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$; ...
user avatar
  • 861
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 ...
user avatar
  • 1,189
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 ...
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 ...
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 ...
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$...
user avatar
2 votes

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\...
user avatar
  • 201

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