All Questions
Tagged with krylov or krylov-method
83 questions
4
votes
0
answers
66
views
Preconditioner for "Generalized stokes" problem
Let $\mu>0$. For the Stokes problem,
\begin{align}
-\mu \Delta u + \nabla p &= f
\\
\nabla \cdot u & = 0
\\
u&= 0 \text{ on } \partial \Omega,
\end{align}
after discretization (say, ...
- 181
0
votes
0
answers
68
views
Improving convergence rate of krylov schur iterations?
I am trying to implement krylov schur iterations. I am noticing that although my implementation converges, it does so really, really slowly. For a 40x40 matrix it is taking hundreds of iterations to ...
- 379
3
votes
1
answer
155
views
How does the Arnoldi iterations algorithm deal with repeated eigenvalues?
The simplest possible matrix I can think of to use an arnoldi method is the identity matrix.
In this case the Krylov sequence is just $\{v, v, v, v, \cdots\}$ for any $v$.
Thus the span of the krylov ...
- 379
2
votes
0
answers
106
views
Iterative solvers for problems in solid and structural mechanics
I am looking for comprehensive literature (papers, books, reports etc..) on iterative solvers for solid and structural mechanics problems to understand the best iterative solvers and preconditioners ...
- 964
3
votes
0
answers
52
views
Preconditioned GMRES for nearly diagonalizable systems
I have been working with a matrix $A$ and preconditioner $P\approx A^{-1}$ that I've then applied GMRES to the (left) preconditioned linear system
\begin{equation}
P^{-1}Ax=P^{-1}b
\end{equation}
$P^{-...
- 189
2
votes
0
answers
101
views
Why multigrid is inefficient？
I am trying to solve the Stokes equation containing viscosity nonlinearity using the open source finite element software underworld2 with nested PETSc. The resolution is 2000*200. The solution results ...
- 21
4
votes
0
answers
138
views
How is the Alternating Schwarz Method used as a Preconditioner to a Krylov Method?
I am reading "Domain Decomposition: Parallel Multilevel Methods for Elliptic Partial Differential Equations" (Smith 1996), and I am confused as to how the below Alternating Schwarz algorithm ...
- 265
2
votes
1
answer
169
views
Ways to fix block Lanczos tridiagonalisation numerical instability for matrix with degenerate, closely spaced eigenvalues?
I want to run a block Lanczos block-tridiagonalization on a hermitian, sparse matrix (of relatively small size $\sim 10^2 \times 10^2$). However the matrix typically has many eigenvalues that are ...
- 21
1
vote
1
answer
210
views
Lanczos memory complexity for dense matrices
Does the Lanczos algorithm remain memory efficient even if the original Hermitian matrix is dense?
- 11
0
votes
0
answers
60
views
Looking for a specific version of the Quasi-Minimal Residual (QMR) method
I'm looking for an alternative formulation of Quasi-Minimal Residual (QMR) from Freund and Nachtigal (1994) based on a Lanczos process for complex valued matrices based on $A^H$ instead of $A^T$.
...
1
vote
0
answers
63
views
Does the choice of a complex inner product affect Krylov methods?
As far as I understand there are two definitions of the complex inner product:
$$(a,b) = b^H a$$
and
$$(a,b) = a^H b$$
I know some linear algebra libraries such as BLAS and Eigen uses the second one.
...
1
vote
1
answer
78
views
Reason for why apparent acceleration of algebraic multigrid solve by addition of positive definite diagonal matrix
In passing I was told by someone that $K^{\prime}\in\mathbb{R}^{n\times n}$, will be easier to solve by an algebraic multigrid preconditioned conjugate gradient (CG-AMG) solver than $K$, where $K$ is ...
- 189
2
votes
1
answer
227
views
Global convergence behavior of several Krylov solvers in scipy.opt
In the context of mechanical simulation, where I solve the stationary action principle directly (i.e. $\nabla S = 0$ for some scalar function $S$), I use the wrapper ...
- 253
4
votes
0
answers
103
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,293
0
votes
0
answers
110
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
71
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(...
- 91
0
votes
2
answers
385
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 ...
- 121
2
votes
0
answers
74
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)|)$ ...
- 445
2
votes
2
answers
780
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. ...
- 33
1
vote
1
answer
173
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,146
1
vote
0
answers
92
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 ...
- 33
1
vote
2
answers
351
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
113
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 ...
- 129
1
vote
2
answers
176
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 ...
- 981
3
votes
0
answers
180
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 ...
- 161
1
vote
0
answers
80
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
2k
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:
...
- 981
1
vote
0
answers
143
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 ...
- 981
3
votes
0
answers
247
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 ...
- 981
5
votes
1
answer
687
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 ...
- 981
2
votes
2
answers
592
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, ...
- 981
2
votes
1
answer
570
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}...
- 981
2
votes
1
answer
805
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 ...
- 981
7
votes
0
answers
371
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
276
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
450
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
19
votes
1
answer
1k
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
477
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
139
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 ...
- 699
1
vote
0
answers
659
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
5
votes
0
answers
117
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 $v$ that belongs to a Krylov subspace $\mathcal{K}_{n+1}(A,b)$ but not to the preceding one ...
- 12.5k
2
votes
1
answer
668
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
445
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 ...
- 191
1
vote
2
answers
237
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
1
vote
1
answer
182
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 ...
- 231
2
votes
0
answers
228
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,423
5
votes
2
answers
726
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
5
votes
2
answers
4k
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 ...
- 161
7
votes
3
answers
2k
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,645
8
votes
2
answers
709
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,225