Questions tagged [krylov-method]
Referring to Krylov Subspaces and the methods of solutions to linear systems of equations which exploit these spaces.
70
questions
3
votes
0answers
64 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 ...
0
votes
0answers
44 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
0answers
50 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(...
0
votes
2answers
165 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 ...
2
votes
0answers
69 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)|)$ ...
1
vote
2answers
316 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. ...
1
vote
1answer
96 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} + \...
1
vote
0answers
82 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 ...
1
vote
2answers
278 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 ...
2
votes
0answers
93 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 ...
1
vote
2answers
116 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 ...
3
votes
0answers
128 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 ...
1
vote
0answers
61 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–...
3
votes
1answer
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:
...
1
vote
0answers
91 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 ...
2
votes
0answers
145 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 ...
5
votes
1answer
550 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 ...
2
votes
2answers
198 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, ...
2
votes
1answer
359 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}...
2
votes
1answer
259 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 ...
7
votes
0answers
237 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, ...
0
votes
0answers
131 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 ...
2
votes
1answer
345 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]-\...
15
votes
1answer
680 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
1answer
297 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, ...
1
vote
1answer
126 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 ...
1
vote
0answers
437 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 ...
1
vote
0answers
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 $\...
2
votes
1answer
427 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,...
4
votes
3answers
323 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 ...
1
vote
2answers
156 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 "...
0
votes
1answer
118 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 ...
2
votes
0answers
163 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 ...
5
votes
2answers
573 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 ...
4
votes
2answers
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 ...
7
votes
3answers
957 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 ...
8
votes
2answers
455 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
votes
0answers
118 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$. ...
2
votes
0answers
267 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....
2
votes
0answers
194 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^...
4
votes
1answer
294 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 ...
4
votes
1answer
268 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 ...
3
votes
1answer
237 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 ...
14
votes
1answer
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$
...
1
vote
0answers
157 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 ...
9
votes
1answer
196 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 ...
9
votes
1answer
510 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
2answers
870 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
0answers
267 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 ...
15
votes
2answers
507 views
Is there any way to do "double preconditioning"
Question:
Suppose that you have two different (factored) preconditioners for a symmetric positive definite matrix $A$:
$$A \approx B^TB$$
and
$$A \approx C^TC,$$
where the inverses of the factors $B, ...