Questions tagged [krylov-method]
Referring to Krylov Subspaces and the methods of solutions to linear systems of equations which exploit these spaces.
71
questions
1
vote
1
answer
98
views
Global convergence behavior of several Krylov solvers in scipy.opt
In a context of mechanical simulation, where I solve the stationnary action principle directly (i.e. $\nabla S = 0$ for some scalar fonction $S$), I use the wrapper scipy.optimize.newton_krylov to ...
- 243
4
votes
0
answers
69
views
Comparing block versus non-block Krylov methods for handling multiple right-hand-sides
Suppose I wish to solve a linear system $AX=B$ iteratively where $A$ is an $m\times m$ matrix and $X,B$ are $m \times s $ matrices (not single vectors). Instead of solving $s$ independent systems I'm ...
- 3,213
0
votes
0
answers
56
views
Help with debugging block GMRES
I have written block version of GMRES by referring [1] and MATLAB implementation of gmres. I need to write it for complex matrices. My block implementation when run on single RHS is giving correct ...
1
vote
0
answers
54
views
Viable algorithms for efficiently solving a block matrix system with non-uniform sparsity structure
I am trying to use Newton's method to get a stationary solution for a system of equations of the following form:
$$
\begin{Bmatrix}
\frac{\partial x}{\partial t} \\
0
\end{Bmatrix} = \begin{Bmatrix}
f(...
- 81
0
votes
2
answers
186
views
Why minimizing with respect to A-norm?
Assume solving the linear system $A \textbf x = \textbf b$, with an $A$ so large that nothing but iterative methods may be employed. Assuming $A$ induces a norm, I realized that it is often desired to ...
- 21
2
votes
0
answers
71
views
Does incomplete LU preconditioning improve the asymptotic scaling of Krylov subspace methods?
It is well known that unpreconditioned Krylov subspace methods applied to the finite-difference-discretised Poisson equation with $n$ grid points per direction require $O(n \, |\log(\varepsilon)|)$ ...
- 405
1
vote
2
answers
404
views
Does LAPACK offer routines for Krylov sub-space based solvers and nonlinear solvers?
I have skimmed through the LAPACK user guide, but I could not find if LAPACK offers routines for Krylov Subspace based methods (such as CG or BiCGSTAB etc) and Newton method based nonlinear solvers. ...
- 23
1
vote
1
answer
100
views
CG without division by 0 in a solution
In the standard formulation of Krylov subspace methods, you always have to divide by 0 somewhere in a solution, e.g., in CG,
$$
x_{k+1} = x_k + \frac{r_k^T r_k}{p_k^T A p_k} p_k\\
p_{k+1} = r_{k+1} + \...
- 3,058
1
vote
0
answers
85
views
2-norm of solution update suddenly becomes zero after a few iterations
I am trying to solve the Poisson equation in 2D for heterostructure devices. I have linearized the equation and discretized it using FDM. I am using BiCGStab to iteratively solve for the solution as ...
- 23
1
vote
2
answers
292
views
How GMRES method finds smallest singular value and the corresponding singular vectors of a matrix?
https://stackoverflow.com
Krylov solvers for iterative computation of the smallest singular value and the corrensponding singular vectors of a matrix
Edit:
This is a follow-up question to How to ...
- 11
2
votes
0
answers
97
views
Solving a huge least squares system of equations when I can only evaluate Ax
I have a situation where I can generate a system of $M$ linear equations for $N$ variables ($N \ne M$). Implicitly this is of the form $Ax=b$ with $A \in \mathbb{R}^{M \times N}$, although I never ...
- 29
1
vote
2
answers
122
views
How to understand the storage of the Hessenberg matrix of Krylov subspace matrix?
For the Krylov subspace method to solve the large sparse linear system, we first need to generate a subspace Km = span{v,Av,...A^{m-1}v}, which indeed a process ...
- 961
3
votes
0
answers
137
views
Solving saddle point problem having non-invertible top-left block with a PETSc nested matrix
My system is a symmetric FE problem with lagrange multipliers:
$Z=\begin{pmatrix}A & C^T \\ C & 0\end{pmatrix}$
The matrix $A$ is positive semi-definite, non-invertible. The whole matrix is ...
- 151
1
vote
0
answers
65
views
Numerical methods. MDF (ILU) implementation
I am trying to implement Minimum Discarded Fill (MDF) Ordering algorithm for incomplete matrix factorization. The algorithm description is here on page 60 Preconditioning Techniques for a Newton–...
- 21
3
votes
1
answer
1k
views
How to implement flexible gmres in matlab?
About the flexible GMRES (fgmres), we know that it is a variant of right preconditioned gmres. And the robust command gmres in matlab as follows:
...
- 961
1
vote
0
answers
100
views
How to compute the computational cost and storage of the Full Orthogonalization Method?
About the analysis of Full Orthogonalization Method (FOM) in Prof. Saad's book, wrote as follows:
Algorithm 6.4 (FOM):
\begin{array}{l}
r_0=b-Ax_0,\beta=\|r_0\|_2,v_1 = r_0/\beta\\
Define \quad H_m ...
- 961
3
votes
0
answers
161
views
How to reproduce the numerical examples in Prof. Saad's Book about Krylov subspace methods?
After reading Prof. Saad' Book, "Iterative methods for Sparse Linear Systems, 2nd version", I want to do the numerical examples about the Krylov subspace methods not only to reproduce the results in ...
- 961
5
votes
1
answer
568
views
Why MATLAB chooses the Householder in its built-in function gmres.m?
Recently, I have studied how to construct an orthonormal basis for Krylov subspace to solve $Ax=b$, where $A\in \mathbb{R}^{n\times n}$ is nonsingular. As we know, there are usually 4 ways to ...
- 961
2
votes
2
answers
231
views
How to understand the choice of Krylov subspace orthonormal basis?
This semester, I study the Krylov subspace iterative methods (about Ax=b) using the book H. A. Van der Vorst. Iterative Krylov Methods for Large Linear Systems,
volume 13. Cambridge University Press, ...
- 961
2
votes
1
answer
400
views
What's wrong with the **PCG and MINRES** in matlab?
Last week, I have learned the details of the robust iterative methods of PCG, MINRES, GMRES, which will converges to the exact solution $x^*$ of nonsingular system within $N$ steps for $A\in \mathbb{R}...
- 961
2
votes
1
answer
310
views
Why Krylov subspace iterative methods are faster than classical iteration?
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 ...
- 961
7
votes
0
answers
283
views
Implementation of Lanczos method that returns tridiagonal matrix
The Lanczos method can be used to obtain extremal eigenpairs of sparse symmetric or hermitian matrices. I know there are several implementations of the Lanczos method (as well as Arnoldi, Davidson, ...
- 171
0
votes
0
answers
152
views
Why does GMRES converge much slower for large Dirichlet boundary conditions?
I'm trying to numerically solve a simple Laplace equation in 2D, with a nonlinear source term:
$\nabla^2 u = u^2$
with boundary conditions as $u=0$ everywhere except for $y=1$ where $u=u_0$. I'm ...
- 101
2
votes
1
answer
363
views
Solving nonlinear PDE with finite difference based on Newton-Krylov
I am now working on solving MHD equations with finite difference method, which include nonlinear equations:
$$
\frac{\partial\rho}{\partial t}+\nabla\cdot\left[\left(\rho_0+\rho\right){v}\right]-\...
- 21
15
votes
1
answer
734
views
What are the major differences between GMRES and FOM?
I am reading Professor Saad's "Iterative Methods for Sparse Linear Systems" (2nd edition).
The basic algorithm for FOM is given on page 166 and the basic algorithm for GMRES is given on page 172.
...
8
votes
1
answer
321
views
How to find a good preconditioner to the system $(A^T A + \lambda I) x = A^T b$?
The system in the title has a damper factor $\lambda > 0$ and the matrix $A$ is sparse and rectangular, with a structure I can exploit to solve matrix vector products very fast. My current solver, ...
- 181
1
vote
1
answer
129
views
Questions about iterative projection methods in Saad book
I am reading Chapter 5 of Saad's iterative methods book, and I don't understand section 5.2.1 about the two propositions of optimality results.
In the statements of the propositions, what does it mean ...
- 649
1
vote
0
answers
483
views
Is reduced stiffness matrix positive definite too?
The stiffness matrix $K$ in a finite element analysis is a symmetric positive definite matrix. When we introduce essential boundary conditions, we remove rows and columns associated with prescribed ...
- 11
1
vote
0
answers
43
views
Name for vectors in a Krylov space but not the preceding one
It seems to me that a useful concept to define when studying Krylov subspace methods is the idea of a vector that belongs to a Krylov subspace $\mathcal{K}_{n+1}(A,b)$ but not to the preceding one $\...
- 8,610
2
votes
1
answer
459
views
Why do we need orthonormal basis of Krylov subspaces for GMRES?
The GMRES method is for solving the linear system $Ax=b$.
Given an initial guess $x_0$ and the corresponding residual $r_0:=b-Ax_0$, we have the Krylov subspace
$$\mathcal{K}_m:=\mathop{span}\{r_0,...
- 1,319
4
votes
3
answers
334
views
For which problems Krylov subspace methods are preferred over multigrid methods?
As multigrid methods are known to have grid independent convergence rates with $O(N)$ computational cost, then why would one be interested in using Krylov subspace methods at all, for which ...
- 181
1
vote
2
answers
169
views
GMRES : incomplete Krylov-subspace
At each iteration $i$ of the GMRES method, is calculated a single new orthonormal vector of the existing Krylov subspace. If the norm of that vector is 0 (or close to 0), then the subspace is "...
- 11
0
votes
1
answer
119
views
Iterative single variable solutions in large linear systems
I have a system where $A$ is a large $n\times n$ marix with fast MVMs. It may have many nonzero entries (albeit in a structured way so as to allow fast MVMs), and is not necessarily diagonally ...
- 201
2
votes
0
answers
175
views
Generalized eigenvalue with null space
Define $S\in\mathbb{R}^{n\times n}$ as
$$S:=H+Q^\top V^{-1} Q.$$
$H,V$ are positive semidefinite. Here, $H$, $Q$, and $V$ are large, dense matrices but they are structured: I can write code for ...
- 1,331
5
votes
2
answers
595
views
PetSc vs Sundials for serial numerical computations?
I am currently working on a physics problem that turns into a non-linear boundary value problem. I need an efficient numerical solver that I could run on my laptop with i5 dual core CPU. I am ...
- 151
4
votes
2
answers
3k
views
A numerical GMRES example
I'm having trouble understanding how GMRES works. I've read the part in Saad's book and a few others but still I am confused. Can someone provide me a numerical example to understand it better? Or if ...
- 151
7
votes
3
answers
1k
views
role of initial guess for iterative linear solver
Suppose we use a preconditioned iterative solver for a linear system. If the initial state for the solver can be chosen very close to the exact solution - does this reduce requirements for the ...
- 2,066
8
votes
2
answers
482
views
Why does conjugate gradient work with this nonsymmetric preconditioner?
In this previous thread the following multiplicative way to combine symmetric preconditioners $P_1$ and $P_2$ for the symmetric system $Ax=b$ was suggested:
\begin{align}
P_\text{combo}^{-1} :=& ...
- 3,013
3
votes
0
answers
122
views
Conjugate gradient: the 1-norm of the residual
I am trying to solve $Ax=b$ using the conjugate gradient method. However, it is important to me to obtain a bound not only on the usual residual $||b-Ax_k||_2$ but also on the quantity $||b-Ax_k||_1$. ...
- 31
2
votes
0
answers
282
views
Does Conjugate Residual really have convergence properties similar to that of Conjugate Gradient?
I have coded up a toy implementation of Conjugate Residual and have been testing it. Both wikipedia and the Saad claim that Conjugate Residual and Conjugate Gradient have similar convergence behavior....
- 1,000
2
votes
0
answers
198
views
preconditioned Uzawa method with Petsc
I am trying to improve the resolution of a Stokes problem (P2/P1 on unstructured mesh) defined by the matrix $M$:
$M=
\begin{pmatrix}
A_u & 0 & B_u \\
0 & A_v & B_v\\
B_u^T & B_v^...
- 65
4
votes
1
answer
310
views
Appropriate iterative linear solver for an eigenvalue problem
I'm trying to solve a generalized eigenvalue problem
$$Ax = \lambda Bx, \quad A = A^\top > 0,\; B = B^\top > 0$$
with $\lambda \approx \sigma$ using Rayleigh Quotient Iteration (RQI) (RQI is ...
- 165
4
votes
1
answer
282
views
Choosing preconditioner for unsymmetric pressure-velocity coupled system
I'm working with pressure-velocity coupled systems. It means that instead of solving 4 different linear systems in segregated approach (1 for pressure and 3 for Ux, Uy, Uz), we can solve only one ...
- 41
3
votes
1
answer
239
views
Trust-region Newton: implementation issue with Conjugate Gradient calculations
UPDATE: The problem turned out to be the step (refer penultimate paragraph below) where I was factoring out a small value from the vectors of the numerator and denominator and then computed dot ...
- 656
14
votes
1
answer
1k
views
How is Krylov-accelerated Multigrid (using MG as a preconditioner) motivated?
Multigrid (MG) may be used to solve a linear system $Ax=b$ by constructing an initial guess $x_0$ and repeating the following for $i=0,1..$ until convergence:
Compute the residual $r_i = b-Ax_i$
...
- 828
1
vote
0
answers
161
views
Search Direction in Conjugate Gradient
Could you help me with a Conjugate Gradient question? In using CG to solve Ax=b, why is the search direction $p_{k+1}$ in CG chosen as a linear combination of the residual $r_k$ and previous direction ...
- 81
9
votes
1
answer
197
views
Guidelines for nested preconditioners
Consider the situation where you want to solve a linear system using a preconditioned Krylov method, but applying the preconditioner itself involves solving an auxiliary system, which is done with ...
- 3,013
9
votes
1
answer
520
views
Algorithm to calculate the exponential of an Hessenberg matrix
I am interested in computing the solution of a lage system of ODEs using a krylov method as in [1]. Such method involve functions related to the exponential (the so-called $\varphi$-functions). It ...
16
votes
2
answers
884
views
Preconditioning a Krylov method with another Krylov method
In methods like gmres or bicgstab it could be attractive to use another Krylov method as a preconditioner. After all they are easy to implement in a matrix-free way and in a parallel environment. For ...
9
votes
0
answers
273
views
Wanted: sequences of linear systems for recycling Krylov solver analysis
In the solution of sequences of linear systems
$$A_ix_i=b_i\quad\text{for}\quad i=1,2,\dots$$
with Krylov subspace methods, data can be recycled from already solved linear systems in order to speed up ...
- 231